Linear Algebra - Find a basis computation problem

> Linear Algebra

1 - About

Find a basis for a vector space

3 - Finding

3.1 - a Basis

3.1.1 - for a null space using

3.1.1.1 - 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])
Advertising

3.1.2 - for a vector space using

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

3.2 - a Subset Basis

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

Advertising

4 - Documentation / Reference

linear_algebra/basis_find.txt · Last modified: 2013/09/20 10:50 by gerardnico