# Linear Algebra - Find a basis computation problem

Find a basis for a vector space

## Finding

### a Basis

#### for a null space using

##### Orthogonal complement

Example:

Find a basis for the null space of $A = \begin{bmatrix} \begin{array}{rrrr} 1 & 0 & 2 & 4 \\ 0 & 5 & 1 & 2 \\ 0 & 2 & 5 & 6 \\ \end{array} \end{bmatrix}$

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 $[1,\frac{1}{10},,\frac{13}{20},\frac{-23}{40}]$ 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 $A = \begin{bmatrix} \begin{array}{rrrr} a_1\\ \hline \\ \vdots \\ \hline \\ a_m \end{array} \end{bmatrix}$ 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 $V=[v_0, \dots , v_n]$ is a list of vectors that are not linearly dependent,

$$\href{dimension}{\text{dim }} \href{span}{\text{Span }} \{v_0, \dots , v_n\} < n + 1 \\$$

The procedure orthogonalize returns a set of vector $V^*=[v^*_0, \dots , v^*_n]$ 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 $V^*$ must conform to this equation:

$$\href{dimension}{\text{dim }} \href{span}{\text{Span }} \{v^*_0, \dots , v^*_n\} = n + 1 \\$$

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 $[v^*_0, \dots , v^*_n]$ without the nonzero vector form then a basis for this vector space (and therefore also for the set $V=[v_0, \dots , v_n]$ ).

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:

$$\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}$$

• Suppose $v^*_1, v^*_4$ are zero vector. Delete zero columns and the corresponding rows of the triangular matrix because for all $\sigma : \sigma_n * v^*_1 = \sigma_n * 0 = 0$

$$\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}$$

• Delete corresponding original columns v1, v4. Resulting triangular matrix is invertible.

$$\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}$$

This equation shows that the $Span \{v_0, v_1 v_2, v_3, v_4, v_5\} \subseteq Span \{v^*_0, v^*_2, v^*_3, v^*_5\}$ so $\{v^*_0, v^*_2, v^*_3, v^*_5\}$ is basis for $V = Span \{v_0, v_1 v_2, v_3, v_4, v_5\}$

• Move the resulting triangular matrix to other side

$$\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}$$

This equation shows that the $Span \{v^*_0, v^*_2, v^*_3, v^*_5\} \subseteq Span \{v_0, v_2, v_3, v_5 \}$ so $\{v_0, v_2, v_3, v_5\}$ is basis for V.

## Documentation / Reference

Discover More
Linear Algebra - Orthogonal complement Vector Space

Let U be a of W. For each vector b in W, we can write b as the following projections: where: is in U, and is orthogonal to every vector in U. Let V be the set . V is the orthogonal complement...