# Linear Algebra - Find a basis computation problem

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 $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])

#### 3.1.2 - for a vector space using

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

### 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:

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