In linear algebra and functional analysis, the kernel (also null space or nullspace) of a linear map L : V → W between two vector spaces V and W, is the set of all elements v of V for which L(v) = 0, where 0 denotes the zero vector in W. That is, in setbuilder notation,

\ker(L) = \left\{ \mathbf{v}\in V  L(\mathbf{v})=\mathbf{0} \right\}\text{.}
Properties of the Kernel
The kernel of L is a linear subspace of the domain V.^{[1]} In the linear map L : V → W, two elements of V have the same image in W if and only if their difference lies in the kernel of L:

L(\mathbf{v}_1) = L(\mathbf{v}_2)\;\;\;\;\Leftrightarrow\;\;\;\;L(\mathbf{v}_1\mathbf{v}_2)=\mathbf{0}\text{.}
It follows that the image of L is isomorphic to the quotient of V by the kernel:

\mathop{\mathrm{im}}(L) \cong V / \ker(L)\text{.}
This implies the rank–nullity theorem:

\dim(\ker L) + \dim(\mathop{\mathrm{im}} L) = \dim(V)\text{.}\,
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 modules
The notion of kernel applies to the homomorphisms of modules, the latter being a generalization of the vector space over a field to that over a ring. The domain of the mapping is a "left and right (algebra) free module", and the kernel constitutes a "submodule". Here, the concepts of rank and nullity do not necessarily apply.
The kernel in functional analysis
If V and W are topological vector spaces (and W is finitedimensional) then a linear operator L: V → W is continuous if and only if the kernel of L is a closed subspace of V.
Representation as matrix multiplication
Consider a linear map represented as a m × n matrix A with coefficients in a field K (typically the field of the real numbers or of the complex numbers) and operating on column vectors x with m components over K. The kernel of this linear map is the set of solutions to the equation A x = 0, where 0 is understood as the zero vector. The dimension of the kernel of A is called the nullity of A. In setbuilder notation,

\operatorname{N}(A)=\operatorname{Null}(A)=\operatorname{ker}(A) = \left\{ \mathbf{x}\in K^n  A\mathbf{x} = \mathbf{0} \right\},.
The matrix equation is equivalent to a homogeneous system of linear equations:

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\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\ a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \;\cdots\; + \;&& a_{mn} x_n &&\; = \;&&& 0\text{.} \\ \end{alignat}
Thus the kernel of A is the same as the solution set to the above homogeneous equations.
Subspace properties
The kernel of an m × n matrix A over a field K is a linear subspace of K^{n}. 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 Matrix
The product Ax can be written in terms of the dot product of vectors as follows:

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 a_{1}, ... , a_{m} 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 (because when the dot product of two vectors is equal to zero, they are by definition orthogonal).
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.
The dimension of the row space of A is called the rank of A, and the dimension of the kernel of A is called the nullity of A. These quantities are related by the rank–nullity theorem

\operatorname{rank}(A) + \operatorname{nullity}(A) = n.
The left null space, or cokernel, of a matrix A consists of all vectors x such that x^{T}A = 0^{T}, where T denotes the transpose of a column vector. The left null space of A is the same as the kernel of A^{T}. The left null space of A is the orthogonal complement to the column space of A, and is 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 equations
The kernel also plays a role in the solution to a nonhomogeneous system of linear equations:

A\mathbf{x}=\mathbf{b}\;\;\;\;\;\;\text{or}\;\;\;\;\;\;\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\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\ a_{m1} x_1 &&\; + \;&& a_{m2} x_2 &&\; + \;\cdots\; + \;&& a_{mn} x_n &&\; = \;&&& b_m \\ \end{alignat}
If u and v are two possible solutions to the above equation, then

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 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

\left\{ \mathbf{v}+\mathbf{x}  A \mathbf{v}=\mathbf{b} \land \mathbf{x}\in\operatorname{Null}(A) \right\},
Geometrically, this says that the solution set to Ax = b is the translation of the kernel of A by the vector v. See also Fredholm alternative and flat (geometry).
Illustration
We give here a simple illustration of computing the kernel of a matrix (see the section Basis below for methods better suited to more complex calculations.) We also touch on the row space and its relation to the kernel.
Consider the matrix

A = \begin{bmatrix}\,\,\,2 & 3 & 5 \\ 4 & 2 & 3\end{bmatrix}.
The kernel of this matrix consists of all vectors (x, y, z) ∈ R^{3} for which

\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 homogeneous system of linear equations involving x, y, and z:

\begin{alignat}{7} 2x &&\; + \;&& 3y &&\; + \;&& 5z &&\; = \;&& 0, \\ 4x &&\; + \;&& 2y &&\; + \;&& 3z &&\; = \;&& 0,\\ \end{alignat}
which can be written in matrix form as:

\left[\begin{array}{cccc} 2 & 3 & 5 & 0 \\ 4 & 2 & 3 & 0 \end{array}\right].
Gauss–Jordan elimination reduces this to:

\left[\begin{array}{cccc} 1 & 0 & 1/16 & 0 \\ 0 & 1 & 13/8 & 0 \end{array}\right].
Rewriting yields:

\begin{alignat}{7} x = \;&& \frac{1}{16}z\,\,\, \\ y = \;&& \frac{13}8z. \end{alignat}
Now we can express an element of the kernel:

\begin{bmatrix} x \\ y \\ z\end{bmatrix} = c \begin{bmatrix} 1/16 \\ 13/8 \\ 1\end{bmatrix}.
for c a scalar.
Since c is a free variable, this can be expressed equally well as,

\begin{bmatrix} x\\ y\\ z \end{bmatrix} = c \begin{bmatrix} 1\\ 26\\ 16 \end{bmatrix}.
The kernel of A is precisely the solution set to these equations (in this case, a line through the origin in R^{3}); the vector (−1,−26,16)^{T} constitutes a basis of the kernel of A. Thus, the nullity of A is 1.
Note also that the following dot products are zero:

\left[\begin{array}{ccc} 2 & 3 & 5 \end{array}\right] \cdot \begin{bmatrix} 1\\ 26\\ 16 \end{bmatrix} = 0 \quad\mathrm{and}\quad \left[\begin{array}{ccc} 4 & 2 & 3 \end{array}\right] \cdot \begin{bmatrix} 1\\ 26\\ 16 \end{bmatrix} = 0\mathrm{,}
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 of A 2, the nullity of A 1, and the dimension of A 3, we have an illustration of the ranknullity theorem.
Examples

If L: R^{m} → R^{n}, 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:


L(x_1,x_2,x_3) = (2x_1 + 3x_2 + 5x_3,\; 4x_1 + 2x_2 + 3x_3)

then the kernel of L is the set of solutions to the equations

\begin{alignat}{7} 2x_1 &\;+\;& 3x_2 &\;+\;& 5x_3 &\;=\;& 0 \\ 4x_1 &\;+\;& 2x_2 &\;+\;& 3x_3 &\;=\;& 0 \end{alignat}

Let C[0,1] denote the vector space of all continuous realvalued functions on the interval [0,1], and define L: C[0,1] → R by the rule


L(f) = f(0.3)\text{.}\,

Then the kernel of L consists of all functions f ∈ C[0,1] for which f(0.3) = 0.

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:


D(f) = \frac{df}{dx}\text{.}

Then the kernel of D consists of all functions in C^{∞}(R) whose derivatives are zero, i.e. the set of all constant functions.


s(x_1,x_2,x_3,x_4,\ldots) = (x_2,x_3,x_4,\ldots)\text{.}

Then the kernel of s is the onedimensional subspace consisting of all vectors (x_{1}, 0, 0, ...).
Computation by Gaussian elimination
A basis of the kernel of a matrix may be computed by Gaussian elimination.
For this purpose, given an m × n matrix A, we construct first the row augmented matrix \left[\begin{array}{c}A\\\hline I\end{array}\right], where I is the n × n identity matrix.
Computing its column echelon form by Gaussian elimination (or any other suitable method), we get a matrix \left[\begin{array}{c}B\\\hline C\end{array}\right]. A basis of the kernel of A consists in the nonzero 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

A=\left[ \begin{array}{cccccc} 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{array} \,\right].
Then

\left[\begin{array}{c}A\\\hline I\end{array}\right]= \left[\begin{array}{cccccc} 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{array}\right].
Putting the upper part in column echelon form by column operations on the whole matrix gives

\left[\begin{array}{c}B\\\hline C\end{array}\right]= \left[\begin{array}{cccccc} 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{array}\right].
The last three columns of B are zero columns. Therefore, the three last vectors of C,

\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 of A.
Numerical computation
The problem of computing the kernel on a computer depends on the nature of the coefficients.
Exact 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, which reduces the problem to a similar one over a finite field.
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 computation
For matrices whose entries are floatingpoint 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 floatingpoint matrix has almost always a full rank, even when it is an approximation of a matrix of a much smaller rank. Even for a fullrank 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.
See also
Notes

^ 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 2005.
References

Axler, Sheldon Jay (1997), Linear Algebra Done Right (2nd ed.), SpringerVerlag,

Lay, David C. (August 22, 2005), Linear Algebra and Its Applications (3rd ed.), Addison Wesley,

Meyer, Carl D. (February 15, 2001), Matrix Analysis and Applied Linear Algebra, Society for Industrial and Applied Mathematics (SIAM),

Poole, David (2006), Linear Algebra: A Modern Introduction (2nd ed.), Brooks/Cole,

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

Serge Lang (1987). Linear Algebra. Springer. p. 59.

Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra, SIAM 1997, ISBN 9780898713619 online version
External links
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.