Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Kernel (linear algebra)

From Wikipedia, the free encyclopedia
(Redirected fromNull space)
Vectors mapped to 0 by a linear map
For other uses, seeKernel (disambiguation).
An example for a kernel- the linear operatorL:(x,y)⟶(x,x){\displaystyle L:(x,y)\longrightarrow (x,x)} transforms all points on the(x=0,y){\displaystyle (x=0,y)} line to the zero point(0,0){\displaystyle (0,0)}, thus they form the kernel for the linear operator

Inmathematics, thekernel of alinear map, also known as thenull space ornullspace, is the part of thedomain which is mapped to thezero vector of theco-domain; the kernel is always alinear subspace of the domain.[1] That is, given a linear mapL :V →W between twovector spacesV andW, the kernel ofL is the vector space of all elementsv ofV such thatL(v) =0, where0 denotes thezero vector inW,[2] or more symbolically:ker⁡(L)={v∈V∣L(v)=0}=L−1(0).{\displaystyle \ker(L)=\left\{\mathbf {v} \in V\mid L(\mathbf {v} )=\mathbf {0} \right\}=L^{-1}(\mathbf {0} ).}

Properties

[edit]
Kernel and image of a linear mapL fromV toW

The kernel ofL is alinear subspace of the domainV.[3][2]

In the linear mapL:V→W,{\displaystyle L:V\to W,} two elements ofV have the sameimage inWif and only if their difference lies in the kernel ofL, that is,

L(v1)=L(v2)⟺L(v1−v2)=0.{\displaystyle L\left(\mathbf {v} _{1}\right)=L\left(\mathbf {v} _{2}\right)\quad \iff \quad L\left(\mathbf {v} _{1}-\mathbf {v} _{2}\right)=\mathbf {0} .}

From this, it follows by thefirst isomorphism theorem that the image ofL isisomorphic to thequotient ofV by the kernel:im⁡(L)≅V/ker⁡(L).{\displaystyle \operatorname {im} (L)\cong V/\ker(L).}In the case whereV isfinite-dimensional, this implies therank–nullity theorem:dim⁡(ker⁡L)+dim⁡(im⁡L)=dim⁡(V).{\displaystyle \dim(\ker L)+\dim(\operatorname {im} L)=\dim(V).}where the termrank refers to the dimension of the image ofL,dim⁡(im⁡L),{\displaystyle \dim(\operatorname {im} L),} whilenullity refers to the dimension of the kernel ofL,dim⁡(ker⁡L).{\displaystyle \dim(\ker L).}[4] That is,Rank⁡(L)=dim⁡(im⁡L) and Nullity⁡(L)=dim⁡(ker⁡L),{\displaystyle \operatorname {Rank} (L)=\dim(\operatorname {im} L)\qquad {\text{ and }}\qquad \operatorname {Nullity} (L)=\dim(\ker L),}so that the rank–nullity theorem can be restated asRank⁡(L)+Nullity⁡(L)=dim⁡(domain⁡L).{\displaystyle \operatorname {Rank} (L)+\operatorname {Nullity} (L)=\dim \left(\operatorname {domain} L\right).}

WhenV is aninner product space, the quotientV/ker⁡(L){\displaystyle V/\ker(L)} can be identified with theorthogonal complement inV ofker⁡(L){\displaystyle \ker(L)}. This is the generalization to linear operators of therow space, orcoimage, of a matrix.

Generalization to modules

[edit]
Main article:Module (mathematics)

The notion of kernel also makes sense forhomomorphisms ofmodules, which are generalizations of vector spaces where the scalars are elements of aring, rather than afield. The domain of the mapping is a module, with the kernel constituting asubmodule. Here, the concepts of rank and nullity do not necessarily apply.

In functional analysis

[edit]
Main article:Topological vector space

IfV andW aretopological vector spaces such thatW is finite-dimensional, then a linear operatorL:V →W iscontinuous if and only if the kernel ofL is aclosed subspace ofV.

Representation as matrix multiplication

[edit]

Consider a linear map represented as am ×n matrixA with coefficients in afieldK (typicallyR{\displaystyle \mathbb {R} } orC{\displaystyle \mathbb {C} }), that is operating on column vectorsx withn components overK.The kernel of this linear map is the set of solutions to the equationAx =0, where0 is understood as thezero vector. Thedimension of the kernel ofA is called thenullity ofA. Inset-builder notation,N⁡(A)=Null⁡(A)=ker⁡(A)={x∈Kn∣Ax=0}.{\displaystyle \operatorname {N} (A)=\operatorname {Null} (A)=\operatorname {ker} (A)=\left\{\mathbf {x} \in K^{n}\mid A\mathbf {x} =\mathbf {0} \right\}.}The matrix equation is equivalent to a homogeneoussystem of linear equations:Ax=0⇔a11x1+a12x2+⋯+a1nxn=0a21x1+a22x2+⋯+a2nxn=0⋮ am1x1+am2x2+⋯+amnxn=0.{\displaystyle A\mathbf {x} =\mathbf {0} \;\;\Leftrightarrow \;\;{\begin{alignedat}{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{alignedat}}}Thus the kernel ofA is the same as the solution set to the above homogeneous equations.

Subspace properties

[edit]

The kernel of am ×n matrixA over a fieldK is alinear subspace ofKn. That is, the kernel ofA, the setNull(A), has the following three properties:

  1. Null(A) always contains thezero vector, sinceA0 =0.
  2. Ifx ∈ Null(A) andy ∈ Null(A), thenx +y ∈ Null(A). This follows from the distributivity ofmatrix multiplication over addition.
  3. Ifx ∈ Null(A) andc is ascalarc ∈K, thencx ∈ Null(A), sinceA(cx) =c(Ax) =c0 =0.

The row space of a matrix

[edit]
Main article:Rank–nullity theorem

The productAx can be written in terms of thedot product of vectors as follows:Ax=[a1⋅xa2⋅x⋮am⋅x].{\displaystyle 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}}.}

Here,a1, ... ,am denote the rows of the matrixA. It follows thatx is in the kernel ofA, if and only ifx isorthogonal (or perpendicular) to each of the row vectors ofA (since orthogonality is defined as having a dot product of 0).

Therow space, or coimage, of a matrixA is thespan of the row vectors ofA. By the above reasoning, the kernel ofA is theorthogonal complement to the row space. That is, a vectorx lies in the kernel ofA, if and only if it is perpendicular to every vector in the row space ofA.

The dimension of the row space ofA is called therank ofA, and the dimension of the kernel ofA is called thenullity ofA. These quantities are related by therank–nullity theorem[4]rank⁡(A)+nullity⁡(A)=n.{\displaystyle \operatorname {rank} (A)+\operatorname {nullity} (A)=n.}

Left null space

[edit]

Theleft null space, orcokernel, of a matrixA consists of all column vectorsx such thatxTA =0T, where T denotes thetranspose of a matrix. The left null space ofA is the same as the kernel ofAT. The left null space ofA is the orthogonal complement to thecolumn space ofA, and is dual to thecokernel of the associated linear transformation. The kernel, the row space, the column space, and the left null space ofA are thefour fundamental subspaces associated with the matrixA.

Nonhomogeneous systems of linear equations

[edit]

The kernel also plays a role in the solution to a nonhomogeneous system of linear equations:Ax=bora11x1+a12x2+⋯+a1nxn=b1a21x1+a22x2+⋯+a2nxn=b2⋮ am1x1+am2x2+⋯+amnxn=bm{\displaystyle A\mathbf {x} =\mathbf {b} \quad {\text{or}}\quad {\begin{alignedat}{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{alignedat}}}Ifu andv are two possible solutions to the above equation, thenA(u−v)=Au−Av=b−b=0{\displaystyle A(\mathbf {u} -\mathbf {v} )=A\mathbf {u} -A\mathbf {v} =\mathbf {b} -\mathbf {b} =\mathbf {0} }Thus, the difference of any two solutions to the equationAx =b lies in the kernel ofA.

It follows that any solution to the equationAx =b can be expressed as the sum of a fixed solutionv and an arbitrary element of the kernel. That is, the solution set to the equationAx =b is{v+x∣Av=b∧x∈Null⁡(A)},{\displaystyle \left\{\mathbf {v} +\mathbf {x} \mid A\mathbf {v} =\mathbf {b} \land \mathbf {x} \in \operatorname {Null} (A)\right\},}Geometrically, this says that the solution set toAx =b is thetranslation of the kernel ofA by the vectorv. See alsoFredholm alternative andflat (geometry).

Illustration

[edit]

The following is a simple illustration of the computation of the kernel of a matrix (see§ Computation by Gaussian elimination, 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 matrixA=[235−423].{\displaystyle A={\begin{bmatrix}2&3&5\\-4&2&3\end{bmatrix}}.}The kernel of this matrix consists of all vectors(x,y,z) ∈R3 for which[235−423][xyz]=[00],{\displaystyle {\begin{bmatrix}2&3&5\\-4&2&3\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}0\\0\end{bmatrix}},}which can be expressed as a homogeneoussystem of linear equations involvingx,y, andz:2x+3y+5z=0,−4x+2y+3z=0.{\displaystyle {\begin{aligned}2x+3y+5z&=0,\\-4x+2y+3z&=0.\end{aligned}}}

The same linear equations can also be written in matrix form as:[2350−4230].{\displaystyle \left[{\begin{array}{ccc|c}2&3&5&0\\-4&2&3&0\end{array}}\right].}

ThroughGauss–Jordan elimination, the matrix can be reduced to:[101/1600113/80].{\displaystyle \left[{\begin{array}{ccc|c}1&0&1/16&0\\0&1&13/8&0\end{array}}\right].}

Rewriting the matrix in equation form yields:x=−116zy=−138z.{\displaystyle {\begin{aligned}x&=-{\frac {1}{16}}z\\y&=-{\frac {13}{8}}z.\end{aligned}}}

The elements of the kernel can be further expressed inparametric vector form, as follows:[xyz]=c[−1/16−13/81](where c∈R){\displaystyle {\begin{bmatrix}x\\y\\z\end{bmatrix}}=c{\begin{bmatrix}-1/16\\-13/8\\1\end{bmatrix}}\quad ({\text{where }}c\in \mathbb {R} )}

Sincec is afree variable ranging over all real numbers, this can be expressed equally well as:[xyz]=c[−1−2616].{\displaystyle {\begin{bmatrix}x\\y\\z\end{bmatrix}}=c{\begin{bmatrix}-1\\-26\\16\end{bmatrix}}.}The kernel ofA is precisely the solution set to these equations (in this case, aline through the origin inR3). Here, the vector(−1,−26,16)T constitutes abasis of the kernel ofA. The nullity ofA is therefore 1, as it is spanned by a single vector.

The following dot products are zero:[235][−1−2616]=0and[−423][−1−2616]=0,{\displaystyle {\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,}which illustrates that vectors in the kernel ofA are orthogonal to each of the row vectors ofA.

These two (linearly independent) row vectors span the row space ofA—a plane orthogonal to the vector(−1,−26,16)T.

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

Examples

[edit]

Computation by Gaussian elimination

[edit]

Abasis of the kernel of a matrix may be computed byGaussian elimination.

For this purpose, given anm ×n matrixA, we construct first the rowaugmented matrix[AI],{\displaystyle {\begin{bmatrix}A\\\hline I\end{bmatrix}},} whereI is then ×nidentity matrix.

Computing itscolumn echelon form by Gaussian elimination (or any other suitable method), we get a matrix[BC].{\displaystyle {\begin{bmatrix}B\\\hline C\end{bmatrix}}.} A basis of the kernel ofA consists in the non-zero columns ofC such that the corresponding column ofB is azero 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 thatA=[10−302−80150−1400017−9000000].{\displaystyle 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}}.}Then[AI]=[10−302−80150−1400017−9000000100000010000001000000100000010000001].{\displaystyle {\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}}.}

Putting the upper part in column echelon form by column operations on the whole matrix gives[BC]=[1000000100000010000000001003−28010−51−40001000010−79000010000001].{\displaystyle {\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}}.}

The last three columns ofB are zero columns. Therefore, the three last vectors ofC,[3−51000],[−210−710],[8−40901]{\displaystyle \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]}are a basis of the kernel ofA.

Proof that the method computes the kernel: Since column operations correspond to post-multiplication by invertible matrices, the fact that[AI]{\displaystyle {\begin{bmatrix}A\\\hline I\end{bmatrix}}} reduces to[BC]{\displaystyle {\begin{bmatrix}B\\\hline C\end{bmatrix}}} means that there exists an invertible matrixP{\displaystyle P} such that[AI]P=[BC],{\displaystyle {\begin{bmatrix}A\\\hline I\end{bmatrix}}P={\begin{bmatrix}B\\\hline C\end{bmatrix}},} withB{\displaystyle B} in column echelon form. ThusAP=B{\displaystyle AP=B},IP=C{\displaystyle IP=C}, andAC=B{\displaystyle AC=B}. A column vectorv{\displaystyle \mathbf {v} } belongs to the kernel ofA{\displaystyle A} (that isAv=0{\displaystyle A\mathbf {v} =\mathbf {0} }) if and only ifBw=0,{\displaystyle B\mathbf {w} =\mathbf {0} ,} wherew=P−1v=C−1v{\displaystyle \mathbf {w} =P^{-1}\mathbf {v} =C^{-1}\mathbf {v} }. AsB{\displaystyle B} is in column echelon form,Bw=0{\displaystyle B\mathbf {w} =\mathbf {0} }, if and only if the nonzero entries ofw{\displaystyle \mathbf {w} } correspond to the zero columns ofB{\displaystyle B}. By multiplying byC{\displaystyle C}, one may deduce that this is the case if and only ifv=Cw{\displaystyle \mathbf {v} =C\mathbf {w} } is a linear combination of the corresponding columns ofC{\displaystyle C}.

Numerical computation

[edit]

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

Exact coefficients

[edit]

If the coefficients of the matrix are exactly given numbers, thecolumn echelon form of the matrix may be computed withBareiss algorithm more efficiently than with Gaussian elimination. It is even more efficient to usemodular arithmetic andChinese remainder theorem, which reduces the problem to several similar ones overfinite fields (this avoids the overhead induced by the non-linearity of thecomputational complexity of integer multiplication).[citation needed]

For coefficients in a finite field, Gaussian elimination works well, but for the large matrices that occur incryptography andGröbner basis computation, better algorithms are known, which have roughly the samecomputational complexity, but are faster and behave better with moderncomputer hardware.[citation needed]

Floating point computation

[edit]

For matrices whose entries arefloating-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 therounding errors, a floating-point matrix has almost always afull 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 iswell conditioned, i.e. it has a lowcondition number.[5][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 theLapack library.[citation needed]

See also

[edit]

Notes and references

[edit]
  1. ^Weisstein, Eric W."Kernel".mathworld.wolfram.com. Retrieved2019-12-09.
  2. ^ab"Kernel (Nullspace) | Brilliant Math & Science Wiki".brilliant.org. Retrieved2019-12-09.
  3. ^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 inLay 2005,Meyer 2001, and Strang's lectures.
  4. ^abWeisstein, Eric W."Rank-Nullity Theorem".mathworld.wolfram.com. Retrieved2019-12-09.
  5. ^"Archived copy"(PDF). Archived fromthe original(PDF) on 2017-08-29. Retrieved2015-04-14.{{cite web}}: CS1 maint: archived copy as title (link)

Bibliography

[edit]
See also:Linear algebra § Further reading

External links

[edit]
Wikibooks has a book on the topic of:Linear Algebra/Null Spaces
Linear equations
Three dimensional Euclidean space
Matrices
Matrix decompositions
Relations and computations
Vector spaces
Structures
Multilinear algebra
Affine and projective
Numerical linear algebra
Retrieved from "https://en.wikipedia.org/w/index.php?title=Kernel_(linear_algebra)&oldid=1323774073"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp