Section02 The Nullspace of A: Solving Ax = 0 and Rx = 0

Nullspace

Defination

• The nullspace $\boldsymbol{N}(\boldsymbol{A})$ consists of all solutions to $\boldsymbol{Ax} = \boldsymbol{0}$. These vector $\boldsymbol{x}$ are in $\mathbb{R}^{n}$
  • When $\boldsymbol{A}$ is Invertible
    • $\boldsymbol{N}(\boldsymbol{A})=\boldsymbol{0}$
  • When $\boldsymbol{A}$ is NOT Invertible
    • solution $\boldsymbol{x} \in \boldsymbol{N}({A})$

Compare to columns space

• Dimension
  • $\boldsymbol{A}$ is a $m \times n$ matrix.
  • The column space of $\boldsymbol{A}$ is a subspace of $\mathbb{R}^{m}$
  • The nullspace of $\boldsymbol{A}$ is a subspace of $\mathbb{R}^{n}$

Describe All solutions

• 2D Vectors
  • Choose the Special Solution $(x_{0}, 1)$, all solutions is the multiplies of this special solution. ($c (x_{0},1)$)
• 3D Vectors
  • Choose two Special Solutions $(x_{01}, 1, 0)$ $(x_{02},0 ,1)$, all other solutions is the linear combination of these two special solutions. ($c_{1}(x_{01},1,0) + c_{2}(x_{02},0,1)$)

Pivot Columns and Free Columns

• The free components correspond to columns with no pivots.

• Suppose $\boldsymbol{A}$ is a $2 \times 2$ matrix which has 2 pivots, the solution of $\boldsymbol{Ax} = \boldsymbol{0}$ is $\boldsymbol{x}$

  • $\boldsymbol{B} = \left[ \begin{matrix} \boldsymbol{A} \\ 2 \boldsymbol{A} \end{matrix} \right]$ has the same solution(2 components vector) of $\boldsymbol{Bx} = \boldsymbol{0}$$\boldsymbol{x}$
    • When we add extra equations(rows) to a matrix, the nullspace certianly can't get larger.
  • $\boldsymbol{C} = \left[ \begin{matrix} \boldsymbol{A} & 2 \boldsymbol{A} \end{matrix} \right]$
    • The solution of $\boldsymbol{Cx} = 0$ has 4 components
    • The first two components is constrainted by pivots (The pivots column of $\boldsymbol{C}$), the others are free (is correspond to the free columns of $\boldsymbol{C}$ ).

• example

• $\boldsymbol{C} = \left[ \begin{matrix} 1 & 2 & 2 & 4 \\ 3 & 8 & 6 & 16 \\ \end{matrix} \right] \Rightarrow \boldsymbol{U} = \left[ \begin{array}{@c{}|@c{}} \textbf{pivot columns} & \textbf{free columns}\\ \begin{matrix} 1 & 2 \\ 0 & 2 \\ \end{matrix} & \begin{matrix} 2 & 4 \\ 0 & 4 \end{matrix} \end{array} \right]$

The Reduced Row Echelon Form $\boldsymbol{R}$

Steps (After Eliminating to $\boldsymbol{U}$)

1. Produce zeros above the pivots.
2. Produce ones in the pivots.

Properties

1. $\boldsymbol{N}(\boldsymbol{A}) = \boldsymbol{N}(\boldsymbol{U}) = \boldsymbol{N}(\boldsymbol{R})$
2. nullspace is easiest to see when we reach the reduced row echelon form $\boldsymbol{R} = \text{rref} (\boldsymbol{A})$
3. The pivot columns of $\boldsymbol{R}$ contain $\boldsymbol{I}$
4. Suppose $\boldsymbol{Ax} = \boldsymbol{0}$ has more unknowns ($n$) than equations ($m$). There must be at least one free column, Then $\boldsymbol{Ax} = \boldsymbol{0}$ has nonzero solutions.
   • at least $n-m$ free variables.
5. The Dimension of nullspace is determinated by the number of free variables.

The Rank of a Matrix

• Defination
  • The rank of $\boldsymbol{A}$ is the number of pivots. This number is $\boldsymbol{r}$
• The true size of $\boldsymbol{A}$ is given by its rank.
• Every "free column" is the linear combination of earlier pivot columns. It is the special solutions tell us those combinations.

Rank one

• just have one pivot.
• The column space of a rank one matrix is "one-dimensional"
• The row space of a rank one matrix is a line.
• The null space of a rank one matrix is the plane perpend to this line of row.

Redefination of Rank

Independency

1. Rank is the number of independent rows of a matrix.
2. Rank is the number of independent columns (pivot columns) of a matrix.

Dimension

1. Rank is the dimension of the column space.
2. Rank is also the dimension of the row space.
3. $n - r$ is the dimension of the nullspace.

Elimination: The Big Picture.

The Questions Elimination ($\boldsymbol{A}\Rightarrow\boldsymbol{U}$) could Answer.

1. Is this columns a combination of previous columns?
2. Is this row a combination of previous rows?

The Questions Reduced Echelon Form ($\boldsymbol{R}$) could answer.

• What those combinations are?

The Bases of Space

Column space of $\boldsymbol{A}$

• Choose the pivot columns of $\boldsymbol{A}$ as a basis.

Row space of $\boldsymbol{A}$

• Choose the nonzero rows of $\boldsymbol{R}$ as a basis.

Nullspace of $\boldsymbol{A}$

• Choose the special solutions to $\boldsymbol{Rx} = \boldsymbol{0}$

Properties from Exercises

• The sum of column space and nullspace's dimension should be less than the $m$ (nmber of rows.)
• Why does no 3 by 3 matrix have a nullspace that equals its column spaces?
  • If nullspace = column space, then $n - r = r \Rightarrow r = \frac{n}{2}$, But $r = \frac{n}{2}$ is impossible because the $n$ is an odd number.
• If $\boldsymbol{AB} = \boldsymbol{0}$, then $\boldsymbol{B}$'s column space is contained in the nullspace of $\boldsymbol{A}$.

• If $\boldsymbol{C} = \left[ \begin{matrix} \boldsymbol{A} \\ \boldsymbol{B} \end{matrix} \right]$, then $\boldsymbol{N}(\boldsymbol{C}) = \boldsymbol{N}(\boldsymbol{A}) \cap \boldsymbol{N}{(\boldsymbol{B})}$

  • $\boldsymbol{Cx} = \boldsymbol{0}$ if and only if $\boldsymbol{Ax} = \boldsymbol{0} \text{ and } \boldsymbol{Bx} = \boldsymbol{0}$

• $r(\boldsymbol{AB}) \le r(\boldsymbol{A} \text{ or } \boldsymbol{B})$

  • proof of $r(\boldsymbol{AB}) \le r(\boldsymbol{B})$ $$\begin{array}{ll} & \text{Suppose the column } j \text{ of } \boldsymbol{B} \text{ is a combination of earlier columns.} \\ \because & \boldsymbol{AB} = \left[ \begin{matrix} \boldsymbol{Ab}_{\boldsymbol{\cdot} 1} & \boldsymbol{Ab}_{\boldsymbol{\cdot} 2} & \cdots & \boldsymbol{Ab}_{\boldsymbol{\cdot} n} \end{matrix} \right] \text{ and } \boldsymbol{b}_{\boldsymbol{\cdot}j} = \sum_{i \ne j}^{n} c_{i}\boldsymbol{b}_{\boldsymbol{\cdot}i} \\ \therefore & \boldsymbol{AB}_{\boldsymbol{\cdot} j} = \boldsymbol{Ab}_{\boldsymbol{\cdot}j} = \boldsymbol{A}\sum_{i \ne j}c_{i}\boldsymbol{b}_{\boldsymbol{\cdot}i} = \sum_{i \ne j} c_{i}\boldsymbol{Ab}_{\boldsymbol{\cdot}i} = \sum_{i \ne j}{c_{i} \boldsymbol{AB}_{\boldsymbol{\cdot}i}} \\ \therefore & \text{The column } j \text{ of } \boldsymbol{AB} \text{ is also a combination of previous columns.} \\ \therefore & r(\boldsymbol{AB}) \le r(\boldsymbol{B}) \\ \end{array}$$
  • proof of $r(\boldsymbol{AB}) \le r(\boldsymbol{A})$ $$\begin{array}{ll} & \text{As the same way, we could prove that: } r(\boldsymbol{B}^{T}\boldsymbol{A}^{T}) \le r(\boldsymbol{A}^{T}) \\ \because & r(\boldsymbol{A}^{T}) = r(\boldsymbol{A}) \\ \therefore & r(\boldsymbol{B}^{T}\boldsymbol{A}^{T}) = r(\boldsymbol{AB}) \le r(\boldsymbol{A}^{T}) = r(\boldsymbol{A}) \\ \end{array}$$

• The nullspace of blockmatrix.

  1. $\boldsymbol{A} = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{I} \end{matrix} \right]$
     • $\boldsymbol{N}(\boldsymbol{A}) = \left[ \begin{matrix} \boldsymbol{I} \\ -\boldsymbol{I} \end{matrix} \right]$
  2. $\boldsymbol{B} = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{I} \\ \boldsymbol{0} & \boldsymbol{0} \end{matrix} \right]$
     • $\boldsymbol{N}(\boldsymbol{B}) = \boldsymbol{N}(\boldsymbol{A}) \left[ \begin{matrix} \boldsymbol{I} \\ -\boldsymbol{I} \end{matrix} \right]$
  3. $\boldsymbol{C} = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{I} & \boldsymbol{I} \end{matrix} \right]$
     • $\boldsymbol{N}(\boldsymbol{C}) = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{I} \\ -\boldsymbol{I} & \boldsymbol{0} \\ \boldsymbol{0} & \boldsymbol{I} \end{matrix} \right]$

• $\color{#D0104C}{\boldsymbol{A} = (\text{pivot column of } \boldsymbol{A})(\text{first } r \text{ rows of } \boldsymbol{R})}$

  • proof $$\begin{array}{ll} & \text{Suppose column } j \text{ of } \boldsymbol{A} \text{ is the combination of previous columns.} \\ \therefore & \boldsymbol{A} = \left[ \begin{matrix} \boldsymbol{a}_{\boldsymbol{\cdot} 1} & \boldsymbol{a}_{\boldsymbol{\cdot} 2} & \cdots & \boldsymbol{a}_{\boldsymbol{\cdot} j} & \cdots & \boldsymbol{a}_{\boldsymbol{\cdot} n} \end{matrix} \right] = \left[ \begin{matrix} \boldsymbol{a}_{\boldsymbol{\cdot} 1} & \boldsymbol{a}_{\boldsymbol{\cdot} 2} & \cdots & \sum_{i \ne j}c_{i}\boldsymbol{a}_{\boldsymbol{\cdot} i} & \cdots & \boldsymbol{a}_{\boldsymbol{\cdot} n} \end{matrix} \right]\\ \because & \boldsymbol{R} = \left[ \begin{matrix} \boldsymbol{I}_{j-1} & \boldsymbol{E} & \boldsymbol{0}_{(j-1)\times (n-j)} \\ \boldsymbol{0}_{(n-j+1) \times (j-1)} & \boldsymbol{0}_{(n-j+1)\times 1} & \boldsymbol{I}_{(n-j+1)} \end{matrix} \right] \text{ and } \boldsymbol{AE} = \boldsymbol{A} \left[ \begin{matrix} \boldsymbol{E} \\ \boldsymbol{0} \end{matrix} \right] = \sum_{i \ne j}(c_{i}\boldsymbol{a}_{\boldsymbol{\cdot}i}) = \boldsymbol{a}_{\boldsymbol{\cdot}j}\\ \therefore & (\text{pivot columns of }\boldsymbol{A})(\text{first } r \text{ rows of } \boldsymbol{R}) \\ & = \left[ \begin{matrix} \boldsymbol{a}_{\boldsymbol{\cdot}1} & \boldsymbol{a}_{\boldsymbol{\cdot}2} & \cdots & \boldsymbol{a}_{\boldsymbol{\cdot}j-1} & \boldsymbol{a}_{\boldsymbol{\cdot}j+1} & \cdots & \boldsymbol{a}_{\boldsymbol{\cdot}n} \end{matrix} \right] \left[ \begin{matrix} \boldsymbol{I}_{j-1} & \boldsymbol{E} & \boldsymbol{0}_{(j-1)\times (n-j)} \\ \boldsymbol{0}_{(n-j+1) \times (j-1)} & \boldsymbol{0}_{(n-j+1)\times 1} & \boldsymbol{I}_{(n-j+1)} \end{matrix} \right] \\ & = \left[ \begin{matrix} \boldsymbol{a}_{\boldsymbol{\cdot} 1} & \boldsymbol{a}_{\boldsymbol{\cdot} 2} & \cdots & \sum_{i \ne j}c_{i}\boldsymbol{a}_{\boldsymbol{\cdot} i} & \cdots & \boldsymbol{a}_{\boldsymbol{\cdot} n} \end{matrix} \right] \\ & = \boldsymbol{A}\\ \end{array}$$
• The reduced echelon form of $\boldsymbol{R}^{T}\boldsymbol{R}$ is always $\boldsymbol{R}$
• proof $$\begin{array}{ll} & \text{Suppose the } \boldsymbol{R} = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{F} \\ \boldsymbol{0} & \boldsymbol{0} \end{matrix} \right] \\ \therefore & \boldsymbol{R}^{T}\boldsymbol{R} = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{0} \\ \boldsymbol{F} & \boldsymbol{0} \end{matrix} \right] \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{F} \\ \boldsymbol{0} & \boldsymbol{0} \end{matrix} \right] = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{F} \\ \boldsymbol{F} & \boldsymbol{F^{2}} \end{matrix} \right]\\ \therefore & \text{The reduced echelon form of } \boldsymbol{R}^{T}\boldsymbol{R} = \\ & \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{F} \\ \boldsymbol{F} - \boldsymbol{I}\boldsymbol{F} & \boldsymbol{F^{2}} - \boldsymbol{F}\boldsymbol{F} \end{matrix} \right] = \left[ \begin{matrix} \boldsymbol{I} & \boldsymbol{F} \\ \boldsymbol{0} & \boldsymbol{0} \end{matrix} \right] = \boldsymbol{R} \\ \end{array}$$