About
Find a basis for a vector space
Articles Related
Finding
a Basis
for a null space using
Orthogonal complement
Example:
Find a basis for the null space of <math> A = \begin{bmatrix} \begin{array}{rrrr} 1 & 0 & 2 & 4 \\ 0 & 5 & 1 & 2 \\ 0 & 2 & 5 & 6 \\ \end{array} \end{bmatrix} </math>
By the dot-product definition of matrix-vector multiplication, a vector v is in the null space of A if the dot-product of each row of A with v is zero.
Thus the null space of A equals the orthogonal complement of Row A in R4.
Since the three rows of A are linearly independent, we know dimRow A = 3…
so the dimension of the orthogonal complement of Row A in R4 is 4 - 3 = 1
The vector <math>[1,\frac{1}{10},,\frac{13}{20},\frac{-23}{40}]</math> has a dot-product of zero with every row of A… so this vector forms a basis for the orthogonal complement. and thus a basis for the null space of A.
Computation: To find basis for null space of an m x n matrix <math> A = \begin{bmatrix} \begin{array}{rrrr} a_1\\ \hline \\ \vdots \\ \hline \\ a_m \end{array} \end{bmatrix} </math> find orthogonal complement of Span {a1, . . . , am} in Rn:
- Let e1, . . . , en be the standard basis vectors Rn.
- Find the nonzero vectors among orthogonalize([a1, . . . , am, e1, . . . , en])
for a vector space using
Orthogonalization
If <math>V=[v_0, \dots , v_n]</math> is a list of vectors that are not linearly dependent,
<MATH> \href{dimension}{\text{dim }} \href{span}{\text{Span }} \{v_0, \dots , v_n\} < n + 1 \\ </MATH>
The procedure orthogonalize returns a set of vector <math>V^*=[v^*_0, \dots , v^*_n]</math> from S that are mutually orthogonal. The length of the two set are the same (ie n+1) and span the same vector space.
But as mutually orthogonal vector are also independent, the set <math>V^*</math> must conform to this equation:
<MATH> \href{dimension}{\text{dim }} \href{span}{\text{Span }} \{v^*_0, \dots , v^*_n\} = n + 1 \\ </MATH>
This is not possible since they span a space of dimension less than n + 1. Therefore some of them must be zero vectors (Leaving out the zero vectors does not change the space spanned).
The subset S of <math>[v^*_0, \dots , v^*_n]</math> without the nonzero vector form then a basis for this vector space (and therefore also for the set <math>V=[v_0, \dots , v_n]</math> ).
def find_basis([v0, . . . , vn]):
“Return the list of nonzero mutually orthogonal vectors.”
[v*0, . . . , v*n] = orthogonalize([v0, . . . , vn])
return [v* for v* in [v*0, ... , v*n] if v* is not the zero vector]
a Subset Basis
using Orthogonalization
Every finite set T of vectors contains a subset S that is a basis for Span T.
def find_subset_basis([v0, . . . , vn]):
“Return the list of original vectors that correspond to nonzero starred vectors.”
[v*0, ... , v*n] = orthogonalize([v0, ... , vn])
Return [vi for i in {0, . . . , n} if v*i is not the zero vector]
# of to overcome the round-off error problem of floating point
Return [vi for i in {0, . . . , n} if squared norms(v*i) are greater than 10**−20]
Proof:
- The matrix equation expressing original vectors in terms of starred vectors (mutually orthogonal vector) is:
<MATH> \begin{bmatrix}v_0 & v_1 & v_2 & v_3 & v_4 & v_5\end{bmatrix} = \begin{bmatrix}v^*_0 & v^*_1 & v^*_2 & v^*_3 & v^*_4 & v^*_5 \end{bmatrix} \begin{bmatrix} 1 & \sigma_{01} & \sigma_{02} & \sigma_{03} & \sigma_{04} & \sigma_{05} \\ & 1 & \sigma_{12} & \sigma_{13} & \sigma_{14} & \sigma_{15} \\ & & 1 & \sigma_{23} & \sigma_{24} & \sigma_{25} \\ & & & 1 & \sigma_{34} & \sigma_{35} \\ & & & & 1 & \sigma_{45} \\ & & & & & 1 \\ \end{bmatrix} </MATH>
- Suppose <math>v^*_1, v^*_4</math> are zero vector. Delete zero columns and the corresponding rows of the triangular matrix because for all <math>\sigma : \sigma_n * v^*_1 = \sigma_n * 0 = 0</math>
<MATH> \begin{bmatrix}v_0 & v_1 & v_2 & v_3 & v_4 & v_5\end{bmatrix} = \begin{bmatrix}v^*_0 & v^*_2 & v^*_3 & v^*_5 \end{bmatrix} \begin{bmatrix} 1 & \sigma_{01} & \sigma_{02} & \sigma_{03} & \sigma_{04} & \sigma_{05} \\ & & 1 & \sigma_{23} & \sigma_{24} & \sigma_{25} \\ & & & 1 & \sigma_{34} & \sigma_{35} \\ & & & & & 1 \\ \end{bmatrix} </MATH>
- Delete corresponding original columns v1, v4. Resulting triangular matrix is invertible.
<MATH> \begin{bmatrix}v_0 & v_2 & v_3 & v_5\end{bmatrix} = \begin{bmatrix}v^*_0 & v^*_2 & v^*_3 & v^*_5 \end{bmatrix} \begin{bmatrix} 1 & \sigma_{02} & \sigma_{03} & \sigma_{05} \\ & 1 & \sigma_{23} & \sigma_{25} \\ & & 1 & \sigma_{35} \\ & & & 1 \\ \end{bmatrix} </MATH>
This equation shows that the <math>Span \{v_0, v_1 v_2, v_3, v_4, v_5\} \subseteq Span \{v^*_0, v^*_2, v^*_3, v^*_5\}</math> so <math>\{v^*_0, v^*_2, v^*_3, v^*_5\}</math> is basis for <math>V = Span \{v_0, v_1 v_2, v_3, v_4, v_5\}</math>
- Move the resulting triangular matrix to other side
<MATH> \begin{bmatrix}v_0 & v_2 & v_3 & v_5\end{bmatrix} {\begin{bmatrix} 1 & \sigma_{02} & \sigma_{03} & \sigma_{05} \\ & 1 & \sigma_{23} & \sigma_{25} \\ & & 1 & \sigma_{35} \\ & & & 1 \\ \end{bmatrix}}^{-1} = \begin{bmatrix}v^*_0 & v^*_2 & v^*_3 & v^*_5 \end{bmatrix} </MATH>
This equation shows that the <math>Span \{v^*_0, v^*_2, v^*_3, v^*_5\} \subseteq Span \{v_0, v_2, v_3, v_5 \}</math> so <math>\{v_0, v_2, v_3, v_5\}</math> is basis for V.