Added to Favorites

Related Searches

Nearby Words

In linear algebra, the kernel or null space (also nullspace) of a matrix A is the set of all vectors x for which Ax = 0. The null space of a matrix with n columns is a linear subspace of n-dimensional Euclidean space.## Finite dimensional linear operator

## Definition

The null space of an m × n matrix A is the set
## Example

Consider the matrix
^{3} for which
## Subspace properties

The null space of an m × n matrix is a subspace of R^{n}. That is, the set Null(A) has the following three properties:## Basis

The null space of a matrix is not affected by elementary row operations. This makes it possible to use row reduction to find a basis for the null space:_{3}, x_{5}, and x_{6} are free, with
## Relation to the row space

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:
_{1}, ..., a_{m} 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.## Nonhomogeneous equations

The null space also plays a role in the solution to a nonhomogeneous system of linear equations:
## Left null space

The left null space 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 null space 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 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.
## Null space of a transformation

If V and W are vector spaces, the null space (or kernel) of a linear transformation T: V → W is the set of all vectors in V that map to zero:
## Numerical computation of null space

## See also

## Notes

## References

### Numerical analysis textbooks

The nullspace (or kernel) of the matrix A is exactly the same thing as the nullspace (or kernel) of the linear mapping defined by the matrix-vector multiplication $mathbf\{x\}\; mapsto\; mathbf\{Ax\}$, that is, the set of vectors that map to the zero vector.

In linear algebra, the null space (also nullspace) of a matrix A is the set of all vectors x for which Ax = 0. The null space of a matrix with n columns is a linear subspace of n-dimensional Euclidean space.

If we regard the matrix as a linear transformation, then the null space is precisely the kernel of the mapping (i.e. the set of vectors that map to zero). For this reason, the kernel of a linear transformation between abstract vector spaces is sometimes referred to as the null space of the transformation.

- $text\{Null\}(mathbf\{A\})\; =\; left\{\; textbf\{x\}intextbf\{R\}^n\; :\; mathbf\{A\}textbf\{x\}\; =\; textbf\{0\}\; right\}text\{,\}$

- $mathbf\{A\}textbf\{x\}=textbf\{0\}\; ;;Leftrightarrow;;\; begin\{alignat\}\{6\}$

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

- $begin\{bmatrix\},,,2\; \&\; 3\; \&\; 5\; -4\; \&\; 2\; \&\; 3end\{bmatrix\}begin\{bmatrix\}\; x\; y\; zend\{bmatrix\}\; =\; begin\{bmatrix\}\; 0\; 0\; end\{bmatrix\}text\{.\}$

- $begin\{alignat\}\{7\}$

2x &&; + ;&& 3y &&; + ;&& 5z &&; = ;&& 0-4x &&; + ;&& 2y &&; + ;&& 3z &&; = ;&& 0. end{alignat} This can be written in matrix form as:

- $begin\{bmatrix\},,,2\; \&\; 3\; \&\; 5\; \&\; 0\; -4\; \&\; 2\; \&\; 3\; \&\; 0end\{bmatrix\}.$

- $begin\{bmatrix\},,,1\; \&\; 0\; \&\; .0625\; \&\; 0\; 0\; \&\; 1\; \&\; 1.625\; \&\; 0end\{bmatrix\}.$

- $begin\{alignat\}\{7\}$

x = ;&& -.0625zy = ;&& -1.625z. end{alignat} Now we can write the null space (solution to Ax = 0) in terms of z (which is our free variable), where z is scalar:

- $z\; begin\{bmatrix\},,,-.0625\; -1.625\; 1end\{bmatrix\}.$

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

- Null(A) always contains the zero vector.
- If x ∈ Null(A) and y ∈ Null(A), then x + y ∈ Null(A).
- If x ∈ Null(A) and c is a scalar, then c x ∈ Null(A).

Here are the proofs:

- A0 = 0.
- If Ax = 0 and Ay = 0, then A(x + y) = Ax + Ay = 0 + 0 = 0.
- If Ax = 0 and c is a scalar, then A(cx) = cAx = c0 = 0.

- Input An m × n matrix A.

- Output A basis for the null space of A

- # Use elementary row operations to put A in reduced row echelon form.

- # Interpreting the reduced row echelon form as a homogeneous linear system, determine which of the variables x
_{1}, x_{2}, ..., x_{n}are free. Write equations for the dependent variables in terms of the free variables.

- # For each free variable x
_{i}, choose the vector in the null space for which x_{i}= 1 and the remaining free variables are zero. The resulting collection of vectors is a basis for the null space of A.

- $left[begin\{alignat\}\{6\}$

- $begin\{alignat\}\{7\}$

- $begin\{array\}\{r\}\; x\_3\; rightarrow\; x\_5\; rightarrow\; x\_6\; rightarrow\; end\{array\}$

left[!! begin{array}{r} 3 -5 mathbf{1} 0 mathbf{0} mathbf{0} end{array} right],; left[!! begin{array}{r} -2 1 mathbf{0} -7 mathbf{1} mathbf{0} end{array} right],; left[!! begin{array}{r} 8 -4 mathbf{0} 9 mathbf{0} mathbf{1} end{array} right] are a basis for the null space of A.

- $mathbf\{A\}textbf\{x\}\; =\; begin\{bmatrix\}\; textbf\{a\}\_1\; cdot\; textbf\{x\}\; textbf\{a\}\_2\; cdot\; textbf\{x\}\; vdots\; textbf\{a\}\_m\; cdot\; textbf\{x\}\; end\{bmatrix\}text\{.\}$

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 null space of A is called the nullity of A. These quantities are related by the equation

- $text\{rank\}(mathbf\{A\})\; +\; text\{nullity\}(mathbf\{A\})\; =\; ntext\{.\},$

- $mathbf\{A\}textbf\{x\}=textbf\{b\};;;;;;text\{or\};;;;;;begin\{alignat\}\{7\}$

- $mathbf\{A\}(textbf\{u\}-textbf\{v\})\; =\; mathbf\{A\}textbf\{u\}\; -\; mathbf\{A\}textbf\{v\}\; =\; textbf\{b\}\; -\; textbf\{b\}\; =\; textbf\{0\},$

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\{\; textbf\{v\}+textbf\{x\}\; ,:,\; textbf\{x\}intext\{Null\}(mathbf\{A\}),\; right\}text\{,\}$

- $ker(T)\; =\; left\{textbf\{v\}in\; V\; :\; T(textbf\{v\})\; =\; textbf\{0\}\; right\}text\{.\}$

Algorithms based on row or column reduction, that is, Gaussian elimination, presented in introductory linear algebra textbooks and in the preceding sections of this article, are not suitable for a practical computation of the null space because of numerical accuracy problems in the presence of rounding errors. Namely, the computation may greatly amplify the rounding errors, which are inevitable in all but textbook examples on integers, and so give completely wrong results. For this reason, methods based on introductory linear algebra texts are generally not suitable for implementation in software; rather, one should consult contemporary numerical analysis sources for an algorithm like the one below, which does not amplify rounding errors unnecessarily.

A state-of-the-art approach is based on singular value decomposition (SVD). This approach can be also easily programmed using standard libraries, such as LAPACK. SVD of matrix A computes unitary matrices U and V and a rectangular diagonal matrix S of the same size as A with nonnegative diagonal entries, such that

- $mathbf\{USV\}\; =\; mathbf\{A\}.$

Denote the columns of V by

- $v\_1,dots,v\_n,$

the diagonal entries of S by

- $s\_1,dots,s\_\{min\{m,n\}\},$

and put

- $s\_\{min\{m,n\}+1\}=cdots=s\_n=0.$

(The numbers $s\_i$ are called the singular values of A.)
Then the columns $v\_i$ of V such that the corresponding $s\_i,=,0$ form an orthonormal basis of the nullspace of A.
In a numerical computation, the singular values $s\_i$ are taken to be zero when they are less than some small tolerance. In the Matlab function `null`

, the tolerance is taken to be

- $max\{m,n\}\; max\; \{s\_i\}\; varepsilon,$

where $varepsilon$ is the machine epsilon of the computer, that is, the smallest number such that in the floating point arithmetics of the computer, $1,+,varepsilon>1$. For the IEEE 64 bit floating point format, $varepsilon,approx,\; 2.2cdot\; 10^\{-16\}$.

Computation of the SVD of a matrix generally costs about the same as several matrix-matrix multiplications with matrices of the same size, when state-of-the art implementation (accurate up to rounding precision) is used, such as in LAPACK. This is true even if, in theory, the SVD cannot be computed by a finite number of operations, so an iterative method with stopping tolerances based on rounding precision must be employed. The cost of the SVD approach is several times higher than computing the null space by reduction, but it should be acceptable whenever reliability is important. It is also possible to compute the null space by the QR decomposition, with the numerical stability and the cost both being between those of the SVD and the reduction approaches. The computation of a null space basis using the QR decomposition is explained in more detail below.

Let A be a mxn matrix with m < n. Using the QR factorization of $mathbf\{A\}^T$, we can find a matrix such that

- $mathbf\{A\}^T\; ,\; mathbf\{P\}\; =\; mathbf\{Q\}\; ,\; mathbf\{R\}\; =\; [mathbf\{Q\}\_1\; ;\; mathbf\{Q\}\_2]\; ,\; mathbf\{R\}$,

- Matrix (mathematics)
- Kernel (algebra)
- Euclidean subspace
- System of linear equations
- Row space
- Column space
- Row reduction
- Four fundamental subspaces

- Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra, SIAM 1997, ISBN 978-0898713619 online version

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday September 09, 2008 at 07:13:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday September 09, 2008 at 07:13:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.