Kernel (linear algebra)
In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map L : V → W between two vector spaces V and W, the kernel of L is the vector space of all elements v of V such that L(v) = 0, where 0 denotes the zero vector in W, or more symbolically:
where, by rank we mean the dimension of the image of L, and by nullity that of the kernel of L.
When V is an inner product space, the quotient V / ker(L) can be identified with the orthogonal complement in V of ker(L). This is the generalization to linear operators of the row space, or coimage, of a matrix.
Application to modulesEdit
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
Representation as matrix multiplicationEdit
Consider a linear map represented as a m × n matrix A with coefficients in a field K (typically or ), that is operating on column vectors x with n components over K. The kernel of this linear map is the set of solutions to the equation Ax = 0, where 0 is understood as the zero vector. The dimension of the kernel of A is called the nullity of A. In set-builder notation,
The matrix equation is equivalent to a homogeneous system of linear equations:
Thus the kernel of A is the same as the solution set to the above homogeneous equations.
The kernel of a m × n matrix A over a field K is a linear subspace of Kn. That is, the kernel of A, the set Null(A), has the following three properties:
- Null(A) always contains the zero vector, since A0 = 0.
- If x ∈ Null(A) and y ∈ Null(A), then x + y ∈ Null(A). This follows from the distributivity of matrix multiplication over addition.
- If x ∈ Null(A) and c is a scalar c ∈ K, then cx ∈ Null(A), since A(cx) = c(Ax) = c0 = 0.
The row space of a matrixEdit
The product Ax can be written in terms of the dot product of vectors as follows:
Here, a1, ... , am denote the rows of the matrix A. It follows that x is in the kernel of A, if and only if x is orthogonal (or perpendicular) to each of the row vectors of A (since orthogonality is defined as having a dot product of 0).
The row space, or coimage, of a matrix A is the span of the row vectors of A. By the above reasoning, the kernel of A is the orthogonal complement to the row space. That is, a vector x lies in the kernel of A, if and only if it is perpendicular to every vector in the row space of A.
Left null spaceEdit
The left null space, or cokernel, of a matrix A consists of all column vectors x such that xTA = 0T, where T denotes the transpose of a matrix. The left null space of A is the same as the kernel of AT. The left null space of A is the orthogonal complement to the column space of A, 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 A are the four fundamental subspaces associated to the matrix A.
Nonhomogeneous systems of linear equationsEdit
The kernel also plays a role in the solution to a nonhomogeneous system of linear equations:
If u and v are two possible solutions to the above equation, then
Thus, the difference of any two solutions to the equation Ax = b lies in the kernel of A.
It follows that any solution to the equation Ax = b can be expressed as the sum of a fixed solution v and an arbitrary element of the kernel. That is, the solution set to the equation Ax = b is
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 matrix
The kernel of this matrix consists of all vectors (x, y, z) ∈ R3 for which
which can be expressed as a homogeneous system of linear equations involving x, y, and z:
The same linear equations can also be written in matrix form as:
Through Gauss–Jordan elimination, the matrix can be reduced to:
Rewriting the matrix in equation form yields:
The elements of the kernel can be further expressed in parametric form, as follows:
Since c is a free variable ranging over all real numbers, this can be expressed equally well as:
The kernel of A is precisely the solution set to these equations (in this case, a line through the origin in R3). Here, since the vector (−1,−26,16)T constitutes a basis of the kernel of A. The nullity of A is 1.
The following dot products are zero:
which illustrates that vectors in the kernel of A are orthogonal to each of the row vectors of A.
These two (linearly independent) row vectors span the row space of A—a plane orthogonal to the vector (−1,−26,16)T.
With the rank 2 of A, the nullity 1 of A, and the dimension 3 of A, we have an illustration of the rank-nullity theorem.
If L: Rm → Rn, then the kernel of L is the solution set to a homogeneous system of linear equations. As in the above illustration, if L is the operator:
Let C[0,1] denote the vector space of all continuous real-valued functions on the interval [0,1], and define L: C[0,1] → R by the rule
Let C∞(R) be the vector space of all infinitely differentiable functions R → R, and let D: C∞(R) → C∞(R) be the differentiation operator:
Let R∞ be the direct product of infinitely many copies of R, and let s: R∞ → R∞ be the shift operator
- If V is an inner product space and W is a subspace, the kernel of the orthogonal projection V → W is the orthogonal complement to W in V.
Computation by Gaussian eliminationEdit
Computing its column echelon form by Gaussian elimination (or any other suitable method), we get a matrix A basis of the kernel of A consists in the non-zero columns of C such that the corresponding column of B 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
Putting the upper part in column echelon form by column operations on the whole matrix gives
The last three columns of B are zero columns. Therefore, the three last vectors of C,
are a basis of the kernel of A.
Proof that the method computes the kernel: Since column operations correspond to post-multiplication by invertible matrices, the fact that reduces to means that there exists an invertible matrix such that with in column echelon form. Thus and A column vector belongs to the kernel of (that is ) if and only where As is in column echelon form, if and only if the nonzero entries of correspond to the zero columns of By multiplying by , one may deduce that this is the case if and only if is a linear combination of the corresponding columns of
The problem of computing the kernel on a computer depends on the nature of the coefficients.
If the coefficients of the matrix are exactly given numbers, the column echelon form of the matrix may be computed by 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).
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.
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.
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 by any of the various algorithms designed to solve homogeneous systems. A state of the art software for this purpose is the Lapack library.
Notes and referencesEdit
- "The Definitive Glossary of Higher Mathematical Jargon — Null". Math Vault. 2019-08-01. Retrieved 2019-12-09.
- Weisstein, Eric W. "Kernel". mathworld.wolfram.com. Retrieved 2019-12-09.
- "Kernel (Nullspace) | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-12-09.
- 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 Lay 2005, Meyer 2001, and Strang's lectures.
- Weisstein, Eric W. "Rank-Nullity Theorem". mathworld.wolfram.com. Retrieved 2019-12-09.
- "Archived copy" (PDF). Archived from the original (PDF) on 2017-08-29. Retrieved 2015-04-14.CS1 maint: archived copy as title (link)
- Axler, Sheldon Jay (1997), Linear Algebra Done Right (2nd ed.), Springer-Verlag, ISBN 0-387-98259-0.
- Lay, David C. (2005), Linear Algebra and Its Applications (3rd ed.), Addison Wesley, ISBN 978-0-321-28713-7.
- Meyer, Carl D. (2001), Matrix Analysis and Applied Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), ISBN 978-0-89871-454-8, archived from the original on 2009-10-31.
- Poole, David (2006), Linear Algebra: A Modern Introduction (2nd ed.), Brooks/Cole, ISBN 0-534-99845-3.
- Anton, Howard (2005), Elementary Linear Algebra (Applications Version) (9th ed.), Wiley International.
- Leon, Steven J. (2006), Linear Algebra With Applications (7th ed.), Pearson Prentice Hall.
- Lang, Serge (1987). Linear Algebra. Springer. ISBN 9780387964126.
- Trefethen, Lloyd N.; Bau, David III (1997), Numerical Linear Algebra, SIAM, ISBN 978-0-89871-361-9.
|Wikibooks has a book on the topic of: Linear Algebra/Null Spaces|