Incubator escapee wiki

Kernel (linear algebra)

Article Discussion

Template:Short description {{#invoke:other uses|otheruses}}

File:Projection-on-diagonal.gif
An example for a kernel- the linear operator <math> L : (x,y) \longrightarrow (x, x)</math> transforms all points on the <math> (x=0, y)</math> line to the zero point <math> (0,0)</math>, thus they form the kernel for the linear operator

In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the part of the domain which is mapped to the zero vector of the co-domain; the kernel is always a linear subspace of the domain.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> That is, given a linear map Template:Math between two vector spaces Template:Mvar and Template:Mvar, the kernel of Template:Mvar is the vector space of all elements Template:Math of Template:Mvar such that Template:Math, where Template:Math denotes the zero vector in Template:Mvar,<ref name=":0">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> or more symbolically: <math display="block">\ker(L) = \left\{ \mathbf{v} \in V \mid L(\mathbf{v})=\mathbf{0} \right\} = L^{-1}(\mathbf{0}).</math>

PropertiesEdit

File:Kernel and image of linear map.svg
Kernel and image of a linear map Template:Mvar from Template:Mvar to Template:Mvar

The kernel of Template:Mvar is a linear subspace of the domain Template:Mvar.<ref name="textbooks">Linear algebra, as discussed in this article, is a very well established mathematical discipline for which there are many sources. Almost all of the material in this article can be found in Template:Harvnb, Template:Harvnb, and Strang's lectures.</ref><ref name=":0" /> In the linear map <math>L : V \to W,</math> two elements of Template:Mvar have the same image in Template:Mvar if and only if their difference lies in the kernel of Template:Mvar, that is, <math display=block>L\left(\mathbf{v}_1\right) = L\left(\mathbf{v}_2\right) \quad \text{ if and only if } \quad L\left(\mathbf{v}_1-\mathbf{v}_2\right) = \mathbf{0}.</math>

From this, it follows by the first isomorphism theorem that the image of Template:Mvar is isomorphic to the quotient of Template:Mvar by the kernel: <math display=block>\operatorname{im}(L) \cong V / \ker(L).</math> Template:AnchorIn the case where Template:Mvar is finite-dimensional, this implies the rank–nullity theorem: <math display=block>\dim(\ker L) + \dim(\operatorname{im} L) = \dim(V).</math> where the term Template:Em refers to the dimension of the image of Template:Mvar, <math>\dim(\operatorname{im} L),</math> while Template:Em refers to the dimension of the kernel of Template:Mvar, <math>\dim(\ker L).</math><ref name=":1">{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> That is, <math display=block>\operatorname{Rank}(L) = \dim(\operatorname{im} L) \qquad \text{ and } \qquad \operatorname{Nullity}(L) = \dim(\ker L),</math> so that the rank–nullity theorem can be restated as <math display=block>\operatorname{Rank}(L) + \operatorname{Nullity}(L) = \dim \left(\operatorname{domain} L\right).</math>

When Template:Mvar is an inner product space, the quotient <math>V / \ker(L)</math> can be identified with the orthogonal complement in Template:Mvar of <math>\ker(L)</math>. This is the generalization to linear operators of the row space, or coimage, of a matrix.

Generalization to modulesEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} The notion of kernel also makes sense for homomorphisms of modules, which are generalizations of vector spaces where the scalars are elements of a ring, rather than a field. The domain of the mapping is a module, with the kernel constituting a submodule. Here, the concepts of rank and nullity do not necessarily apply.

In functional analysisEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} If Template:Mvar and Template:Mvar are topological vector spaces such that Template:Mvar is finite-dimensional, then a linear operator Template:Math is continuous if and only if the kernel of Template:Mvar is a closed subspace of Template:Mvar.

Representation as matrix multiplicationEdit

Consider a linear map represented as a Template:Math matrix Template:Mvar with coefficients in a field Template:Mvar (typically <math>\mathbb{R}</math> or <math>\mathbb{C}</math>), that is operating on column vectors Template:Math with Template:Mvar components over Template:Mvar. The kernel of this linear map is the set of solutions to the equation Template:Math, where Template:Math is understood as the zero vector. The dimension of the kernel of A is called the nullity of A. In set-builder notation, <math display="block">\operatorname{N}(A) = \operatorname{Null}(A) = \operatorname{ker}(A) = \left\{ \mathbf{x}\in K^n \mid A\mathbf{x} = \mathbf{0} \right\}.</math> The matrix equation is equivalent to a homogeneous system of linear equations: <math display="block">A\mathbf{x}=\mathbf{0} \;\;\Leftrightarrow\;\; \begin{alignat}{7} a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \;\cdots\; + \;&& a_{1n} x_n &&\; = \;&&& 0 \\ a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \;\cdots\; + \;&& a_{2n} x_n &&\; = \;&&& 0 \\ 

          &&       &&            &&                    &&            &&\vdots\ \;&&&    \\

a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \;\cdots\; + \;&& a_{mn} x_n &&\; = \;&&& 0\text{.} \\ \end{alignat}</math> Thus the kernel of A is the same as the solution set to the above homogeneous equations.

Subspace propertiesEdit

The kernel of a Template:Math matrix Template:Mvar over a field Template:Mvar is a linear subspace of Template:Math. That is, the kernel of Template:Mvar, the set Template:Math, has the following three properties:

  1. Template:Math always contains the zero vector, since Template:Math.
  2. If Template:Math and Template:Math, then Template:Math. This follows from the distributivity of matrix multiplication over addition.
  3. If Template:Math and Template:Mvar is a scalar Template:Math, then Template:Math, since Template:Math.

The row space of a matrixEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} The product Ax can be written in terms of the dot product of vectors as follows: <math display="block">A\mathbf{x} = \begin{bmatrix} \mathbf{a}_1 \cdot \mathbf{x} \\ \mathbf{a}_2 \cdot \mathbf{x} \\ \vdots \\ \mathbf{a}_m \cdot \mathbf{x} \end{bmatrix}.</math>

Here, Template:Math denote the rows of the matrix Template:Mvar. It follows that Template:Math is in the kernel of Template:Mvar, if and only if Template:Math is orthogonal (or perpendicular) to each of the row vectors of Template:Mvar (since orthogonality is defined as having a dot product of 0).

The row space, or coimage, of a matrix Template:Mvar is the span of the row vectors of Template:Mvar. By the above reasoning, the kernel of Template:Mvar is the orthogonal complement to the row space. That is, a vector Template:Math lies in the kernel of Template:Mvar, if and only if it is perpendicular to every vector in the row space of Template:Mvar.

The dimension of the row space of Template:Mvar is called the rank of A, and the dimension of the kernel of Template:Mvar is called the nullity of Template:Mvar. These quantities are related by the rank–nullity theorem<ref name=":1" /> <math display="block">\operatorname{rank}(A) + \operatorname{nullity}(A) = n.</math>

Left null spaceEdit

The left null space, or cokernel, of a matrix Template:Mvar consists of all column vectors Template:Math such that Template:Math, where T denotes the transpose of a matrix. The left null space of Template:Mvar is the same as the kernel of Template:Math. The left null space of Template:Mvar is the orthogonal complement to the column space of Template:Mvar, and is dual to the cokernel of the associated linear transformation. The kernel, the row space, the column space, and the left null space of Template:Mvar are the four fundamental subspaces associated with the matrix Template:Mvar.

Nonhomogeneous systems of linear equationsEdit

The kernel also plays a role in the solution to a nonhomogeneous system of linear equations: <math display="block">A\mathbf{x} = \mathbf{b}\quad \text{or} \quad \begin{alignat}{7} a_{11} x_1 &&\; + \;&& a_{12} x_2 &&\; + \;\cdots\; + \;&& a_{1n} x_n &&\; = \;&&& b_1 \\ a_{21} x_1 &&\; + \;&& a_{22} x_2 &&\; + \;\cdots\; + \;&& a_{2n} x_n &&\; = \;&&& b_2 \\ 

          &&       &&            &&                    &&            &&\vdots\ \;&&&       \\

a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \;\cdots\; + \;&& a_{mn} x_n &&\; = \;&&& b_m \\ \end{alignat}</math> If Template:Math and Template:Math are two possible solutions to the above equation, then <math display="block">A(\mathbf{u} - \mathbf{v}) = A\mathbf{u} - A\mathbf{v} = \mathbf{b} - \mathbf{b} = \mathbf{0}</math> Thus, the difference of any two solutions to the equation Template:Math lies in the kernel of Template:Mvar.

It follows that any solution to the equation Template:Math can be expressed as the sum of a fixed solution Template:Math and an arbitrary element of the kernel. That is, the solution set to the equation Template:Math is <math display="block">\left\{ \mathbf{v}+\mathbf{x} \mid A \mathbf{v}=\mathbf{b} \land \mathbf{x}\in\operatorname{Null}(A) \right\},</math> Geometrically, this says that the solution set to Template:Math is the translation of the kernel of Template:Mvar by the vector Template:Math. See also Fredholm alternative and flat (geometry).

IllustrationEdit

The following is a simple illustration of the computation of the kernel of a matrix (see Template:Slink, below for methods better suited to more complex calculations). The illustration also touches on the row space and its relation to the kernel.

Consider the matrix <math display="block">A = \begin{bmatrix} 2 & 3 & 5 \\ -4 & 2 & 3 \end{bmatrix}.</math> The kernel of this matrix consists of all vectors Template:Math for which <math display="block">\begin{bmatrix} 2 & 3 & 5 \\ -4 & 2 & 3 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix},</math> which can be expressed as a homogeneous system of linear equations involving Template:Mvar, Template:Mvar, and Template:Mvar: <math display="block">\begin{align} 

2x + 3y + 5z &= 0, \\

-4x + 2y + 3z &= 0. \end{align}</math>

The same linear equations can also be written in matrix form as: <math display="block"> 

 \left[\begin{array}{ccc|c}
   2 & 3 & 5 & 0 \\
   -4 & 2 & 3 & 0
 \end{array}\right].

</math>

Through Gauss–Jordan elimination, the matrix can be reduced to: <math display="block"> 

 \left[\begin{array}{ccc|c}
   1 & 0 & 1/16 & 0 \\
   0 & 1 & 13/8 & 0
 \end{array}\right].

</math>

Rewriting the matrix in equation form yields: <math display="block">\begin{align} x &= -\frac{1}{16}z \\ y &= -\frac{13}{8}z. \end{align}</math>

The elements of the kernel can be further expressed in parametric vector form, as follows: <math display="block">\begin{bmatrix} x \\ y \\ z\end{bmatrix} = c \begin{bmatrix} -1/16 \\ -13/8 \\ 1\end{bmatrix}\quad (\text{where }c \in \mathbb{R})</math>

Since Template:Mvar is a free variable ranging over all real numbers, this can be expressed equally well as: <math display="block"> \begin{bmatrix} x \\ y \\ z \end{bmatrix} 

= c \begin{bmatrix} -1 \\ -26 \\ 16 \end{bmatrix}.

</math> The kernel of Template:Mvar is precisely the solution set to these equations (in this case, a line through the origin in Template:Math). Here, the vector Template:Math constitutes a basis of the kernel of Template:Mvar. The nullity of Template:Mvar is therefore 1, as it is spanned by a single vector.

The following dot products are zero: <math display="block"> 

\begin{bmatrix} 2 & 3 & 5 \end{bmatrix}
\begin{bmatrix} -1 \\ -26 \\ 16 \end{bmatrix}

= 0 \quad\mathrm{and}\quad 

\begin{bmatrix} -4 & 2 & 3 \end{bmatrix}
\begin{bmatrix} -1 \\ -26 \\ 16 \end{bmatrix}

= 0 , </math> which illustrates that vectors in the kernel of Template:Mvar are orthogonal to each of the row vectors of Template:Mvar.

These two (linearly independent) row vectors span the row space of Template:Mvar—a plane orthogonal to the vector Template:Math.

With the rank 2 of Template:Mvar, the nullity 1 of Template:Mvar, and the dimension 3 of Template:Mvar, we have an illustration of the rank-nullity theorem.

ExamplesEdit

  • If Template:Math, then the kernel of Template:Math is the solution set to a homogeneous system of linear equations. As in the above illustration, if Template:Math is the operator: <math display="block"> L(x_1, x_2, x_3) = (2 x_1 + 3 x_2 + 5 x_3,\; - 4 x_1 + 2 x_2 + 3 x_3)</math> then the kernel of Template:Math is the set of solutions to the equations <math display="block"> \begin{alignat}{7}
   2x_1 &\;+\;& 3x_2 &\;+\;& 5x_3 &\;=\;& 0 \\
  -4x_1 &\;+\;& 2x_2 &\;+\;& 3x_3 &\;=\;& 0

\end{alignat}</math>

Computation by Gaussian eliminationEdit

A basis of the kernel of a matrix may be computed by Gaussian elimination.

For this purpose, given an Template:Math matrix Template:Mvar, we construct first the row augmented matrix <math> \begin{bmatrix}A \\ \hline I \end{bmatrix},</math> where Template:Math is the Template:Math identity matrix.

Computing its column echelon form by Gaussian elimination (or any other suitable method), we get a matrix <math> \begin{bmatrix} B \\\hline C \end{bmatrix}.</math> A basis of the kernel of Template:Mvar consists in the non-zero columns of Template:Mvar such that the corresponding column of Template:Mvar is a zero column.

In fact, the computation may be stopped as soon as the upper matrix is in column echelon form: the remainder of the computation consists in changing the basis of the vector space generated by the columns whose upper part is zero.

For example, suppose that <math display="block">A = \begin{bmatrix} 1 & 0 & -3 & 0 & 2 & -8 \\ 0 & 1 & 5 & 0 & -1 & 4 \\ 0 & 0 & 0 & 1 & 7 & -9 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}. </math> Then <math display="block"> \begin{bmatrix} A \\ \hline I \end{bmatrix} = \begin{bmatrix} 1 & 0 & -3 & 0 & 2 & -8 \\ 0 & 1 & 5 & 0 & -1 & 4 \\ 0 & 0 & 0 & 1 & 7 & -9 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}. </math>

Putting the upper part in column echelon form by column operations on the whole matrix gives <math display="block"> \begin{bmatrix} B \\ \hline C \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 3 & -2 & 8 \\ 0 & 1 & 0 & -5 & 1 & -4 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & -7 & 9 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}. </math>

The last three columns of Template:Mvar are zero columns. Therefore, the three last vectors of Template:Mvar, <math display="block">\left[\!\! \begin{array}{r} 3 \\ -5 \\ 1 \\ 0 \\ 0 \\ 0 \end{array} \right] ,\; \left[\!\! \begin{array}{r} -2 \\ 1 \\ 0 \\ -7 \\ 1 \\ 0 \end{array} \right],\; \left[\!\! \begin{array}{r} 8 \\ -4 \\ 0 \\ 9 \\ 0 \\ 1 \end{array} \right] </math> are a basis of the kernel of Template:Mvar.

Proof that the method computes the kernel: Since column operations correspond to post-multiplication by invertible matrices, the fact that <math>\begin{bmatrix} A \\ \hline I \end{bmatrix}</math> reduces to <math>\begin{bmatrix} B \\ \hline C \end{bmatrix}</math> means that there exists an invertible matrix <math>P</math> such that <math> \begin{bmatrix} A \\ \hline I \end{bmatrix} P = \begin{bmatrix} B \\ \hline C \end{bmatrix}, </math> with <math>B</math> in column echelon form. Thus Template:Nowrap Template:Nowrap and Template:Nowrap A column vector <math>\mathbf v</math> belongs to the kernel of <math>A</math> (that is <math>A \mathbf v = \mathbf 0</math>) if and only if <math>B \mathbf w = \mathbf 0,</math> where Template:Nowrap As <math>B</math> is in column echelon form, Template:Nowrap if and only if the nonzero entries of <math>\mathbf w</math> correspond to the zero columns of Template:Nowrap By multiplying by Template:Nowrap one may deduce that this is the case if and only if <math>\mathbf v = C \mathbf w</math> is a linear combination of the corresponding columns of Template:Nowrap

Numerical computationEdit

The problem of computing the kernel on a computer depends on the nature of the coefficients.

Exact coefficientsEdit

If the coefficients of the matrix are exactly given numbers, the column echelon form of the matrix may be computed with Bareiss algorithm more efficiently than with Gaussian elimination. It is even more efficient to use modular arithmetic and Chinese remainder theorem, which reduces the problem to several similar ones over finite fields (this avoids the overhead induced by the non-linearity of the computational complexity of integer multiplication).Template:Citation needed

For coefficients in a finite field, Gaussian elimination works well, but for the large matrices that occur in cryptography and Gröbner basis computation, better algorithms are known, which have roughly the same computational complexity, but are faster and behave better with modern computer hardware.Template:Citation needed

Floating point computationEdit

For matrices whose entries are floating-point numbers, the problem of computing the kernel makes sense only for matrices such that the number of rows is equal to their rank: because of the rounding errors, a floating-point matrix has almost always a full rank, even when it is an approximation of a matrix of a much smaller rank. Even for a full-rank matrix, it is possible to compute its kernel only if it is well conditioned, i.e. it has a low condition number.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>Template:Citation needed

Even for a well conditioned full rank matrix, Gaussian elimination does not behave correctly: it introduces rounding errors that are too large for getting a significant result. As the computation of the kernel of a matrix is a special instance of solving a homogeneous system of linear equations, the kernel may be computed with any of the various algorithms designed to solve homogeneous systems. A state of the art software for this purpose is the Lapack library.Template:Citation needed

See alsoEdit

Template:Div col

Template:Div col end

Notes and referencesEdit

Template:Reflist

BibliographyEdit

Template:See also Template:Refbegin

Template:Refend

External linksEdit

Template:Sister project

{{#invoke:Navbox|navbox}}

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Kernel_(linear_algebra)&oldid=627799"