Kernel (linear algebra)

From Wikipedia, the free encyclopedia
  (Redirected from Kernel (matrix))
Jump to: navigation, search

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

\ker(L) = \left\{ v\in V : L(v)=0 \right\}\text{,}

where 0 denotes the zero vector in W. The kernel of L is a linear subspace of the domain V.[1] For a linear map given as a matrix A, the kernel is simply the set of solutions to the equation Ax = 0, where x and 0 are understood to be column vectors. The dimension of the null space of A is called the nullity of A.

Definition[edit]

The kernel of a m × n matrix A with coefficients in a field K (typically the field of the real numbers or of the complex numbers) is the set

\operatorname{N}(A)=\operatorname{Null}(A)=\operatorname{ker}(A) = \left\{ \mathbf{x}\in K^n : A\mathbf{x} = \mathbf{0} \right\},[2]

where 0 denotes the zero vector with m components. The matrix equation Ax = 0 is equivalent to a homogeneous system of linear equations:

A\mathbf{x}=\mathbf{0} \;\;\Leftrightarrow\;\;  \begin{alignat}{6}
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. &
\end{alignat}

From this viewpoint, the null space of A is the same as the solution set to the homogeneous system.

The same definition fits for matrices over a ring K, replacing the "vector n-space" with "right free module" and a "linear subspace" with "submodule", but there is no concept of nullity.

Computation[edit]

In this section, we show on a very simple example how the null space of a matrix may be computed. However the method which is sketched here is not practical for effective computations. A more efficient method is presented below.

Consider the matrix

A = \begin{bmatrix}\,\,\,2 & 3 & 5 \\ -4 & 2 & 3\end{bmatrix}.

The null space of this matrix consists of all vectors (x, y, z) ∈ R3 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}.

This can be written 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}

This can be written in matrix form as:


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

Using Gauss–Jordan elimination, this reduces to:


  \left[\begin{array}{ccc|c}
    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 write the null space (solution to Ax = 0) in terms of c, where c is scalar:

\begin{bmatrix} x \\ y \\ z\end{bmatrix} = c \begin{bmatrix} -1/16 \\ -13/8 \\ 1\end{bmatrix}.

Since c is a free variable this can be simplified to


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

The null space of A is precisely the set of solutions to these equations (in this case, a line through the origin in R3).

Examples[edit]

  • If LRm → Rn, then the kernel of L is the solution set to a homogeneous system of linear equations. For example, if L is the operator:
L(x_1,x_2,x_3) = (2x_1 + 5x_2 - 3x_3,\; 4x_1 + 2x_2 + 7x_3)
then the kernel of L is the set of solutions to the equations
\begin{alignat}{7}
 2x_1 &&\; + \;&& 5x_2 &&\; - \;&& 3x_3 &&\; = \;&& 0 \\
 4x_1 &&\; + \;&& 2x_2 &&\; + \;&& 7x_3 &&\; = \;&& 0 .
\end{alignat}
  • Let C[0,1] denote the vector space of all continuous real-valued functions on the interval [0,1], and define LC[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 DC(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 one-dimensional subspace consisting of all vectors (x1, 0, 0, ...).

Subspace properties[edit]

The null space of an m × n real matrix is a linear subspace of Rn. That is, the set Null(A) has the following three properties:

  1. Null(A) always contains the zero vector, since A0 = 0.
  2. If x ∈ Null(A) and y ∈ Null(A), then x + y ∈ Null(A). This follows from the distributivity of matrix multiplication over addition.
  3. If x ∈ Null(A) and c is a scalar, then cx ∈ Null(A), since A(cx) = c(Ax) = c0 = 0.

If LV → W, then two elements of V have the same image in W if and only if their difference lies in the kernel of L:

L(v_1) = L(v_2)\;\;\;\;\Leftrightarrow\;\;\;\;L(v_1-v_2)=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{.}\,

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 of a matrix.

Basis[edit]

A basis of the null space 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 available method), we get a matrix  \left[\begin{array}{c}B\\\hline C\end{array}\right]. A basis of the null space 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

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 null space of A.

Relation to the row space[edit]

Let A be an m by n matrix (i.e., A has m rows and n columns). The product of A and the n-dimensional vector x 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 a1, ... , am denote the rows of the matrix A. It follows that x is in the null space of A if and only if x is orthogonal (or perpendicular) to each of the row vectors of A (because if the dot product of two vectors is equal to zero they are by definition orthogonal).

The row space of a matrix A is the span of the row vectors of A. By the above reasoning, the null space of A is the orthogonal complement to the row space. That is, a vector x lies in the null space 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 null space of A is called the nullity of A. These quantities are related by the equation

\operatorname{rank}(A) + \operatorname{nullity}(A) = n.

The equation above is known as the rank–nullity theorem.

Nonhomogeneous equations[edit]

The null space 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 null space 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 null space. That is, the solution set to the equation Ax = b is

\left\{ \mathbf{v}+\mathbf{x} \,:\, \mathbf{x}\in\operatorname{Null}(A)\, \right\},

where v is any fixed vector satisfying Av = b. Geometrically, this says that the solution set to Ax = b is the translation of the null space of A by the vector v. See also Fredholm alternative and flat (geometry).

Left null space[edit]

The left null space of a matrix A consists of all vectors x such that xTA = 0T, where T denotes the transpose of a column vector. The left null space of A is the same as the null space of AT. 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 null space, the row space, the column space, and the left null space of A are the four fundamental subspaces associated to the matrix A.

Kernels in functional analysis[edit]

If V and W are topological vector spaces (and W is finite-dimensional) then a linear operator LV → W is continuous if and only if the kernel of L is a closed subspace of V.

Numerical computation[edit]

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

Exact coefficients[edit]

If the coefficients of the matrix are exactly given integers 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[edit]

For matrices whose entries are floating-point numbers, the problem of computing the null space 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 null space 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 null space of a matrix is a special instance of solving a homogeneous system of linear equations, the null space 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[edit]

Notes[edit]

  1. ^ 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.
  2. ^ This equation uses set-builder notation.

References[edit]

  • Axler, Sheldon Jay (1997), Linear Algebra Done Right (2nd ed.), Springer-Verlag, ISBN 0-387-98259-0 
  • Lay, David C. (August 22, 2005), Linear Algebra and Its Applications (3rd ed.), Addison Wesley, ISBN 978-0-321-28713-7 
  • Meyer, Carl D. (February 15, 2001), Matrix Analysis and Applied Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), ISBN 978-0-89871-454-8 
  • 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 
  • Serge Lang (1987). Linear Algebra. Springer. p. 59. ISBN 9780387964126. 
  • Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra, SIAM 1997, ISBN 978-0-89871-361-9 online version

External links[edit]