Skip to main content

Null Space - Reduced row echelon form

Previously we saw how to get echelon form, pivot/free column vectors of a matrix say AA also saw how to solve Ax⃗=0A\vec{x}=0.
Now let's push it little further and see the reduce row echelon form of our matrix AA.

Reduced Row Echelon Form​

In reduced row echelon form we use elimination and make all elements 00 above and below pivot elements.

We saw the echelon form of

A=[1222246836810]A=\begin{bmatrix} 1 & 2 & 2 & 2\\ 2 & 4 & 6 & 8\\ 3 & 6 & 8 & 10\\ \end{bmatrix}

is say UU

U=[122200240000]U=\begin{bmatrix} \fbox{1} & 2 & 2 & 2\\ 0 & 0 & \fbox{2} & 4\\ 0 & 0 & 0 & 0\\ \end{bmatrix}

Now we make element above pivot =0=0
So let's use elimination to do it.

U=[122200240000]U=\begin{bmatrix} \fbox{1} & 2 & 2 & 2\\ 0 & 0 & \fbox{2} & 4\\ 0 & 0 & 0 & 0\\ \end{bmatrix}

r1←r1−r2r_1\leftarrow r_1-r_2

U′=[120−200240000]U'=\begin{bmatrix} \fbox{1} & 2 & 0 & -2\\ 0 & 0 & \fbox{2} & 4\\ 0 & 0 & 0 & 0\\ \end{bmatrix}

Now make pivot elements =1=1
r2←r2/2r_2\leftarrow r_2/2

U′=[120−200120000]U'=\begin{bmatrix} \fbox{1} & 2 & 0 & -2\\ 0 & 0 & \fbox{1} & 2\\ 0 & 0 & 0 & 0\\ \end{bmatrix}

Say this matrix is RR.

R=[120−200120000]R=\begin{bmatrix} \color{DC143C}{\fbox{1}} & \color{318CE7}{2} & \color{DC143C}{0} & \color{318CE7}{-2} \\ \color{DC143C}{0} & \color{318CE7}{0} & \color{DC143C}{\fbox{1}} & \color{318CE7}{2} \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}

Here you can see that there is a 2×22\times 2 Identity matrix shown in red\color{DC143C}{\text{red}} and one more 2×22\times 2 matrix shown in blue\color{318CE7}{\text{blue}}
So RR is something like:

R′=[IF00]R'=\begin{bmatrix} \color{DC143C}{\text{I}} & \color{318CE7}{\text{F}} \\ 0 & 0 \\ \end{bmatrix}

and here

I=[1001] and F=[2−202]\color{DC143C}{ I=\begin{bmatrix} 1&0\\0&1\\ \end{bmatrix} } \text{ and } \color{318CE7}{ F=\begin{bmatrix} 2&-2\\0&2\\ \end{bmatrix} }
note

Here you can see that there is some reordering of columns but it's fine.
Because we are striving for x⃗\vec{x} that solves Rx⃗=0R\vec{x}=0

Rx⃗=[120−200120000][x1x2x3x4]=0R\vec{x}=\begin{bmatrix} \color{DC143C}{\fbox{1}} & \color{318CE7}{2} & \color{DC143C}{0} & \color{318CE7}{-2} \\ \color{DC143C}{0} & \color{318CE7}{0} & \color{DC143C}{\fbox{1}} & \color{318CE7}{2} \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} \color{DC143C}{x_1}\\\color{318CE7}{x_2}\\\color{DC143C}{x_3}\\\color{318CE7}{x_4}\\ \end{bmatrix} =0

We can also write it as:

R′x⃗′=[102−201020000][x1x3x2x4]=0R'\vec{x}'=\begin{bmatrix} \color{DC143C}{\fbox{1}} & \color{DC143C}{0} & \color{318CE7}{2} & \color{318CE7}{-2} \\ \color{DC143C}{0} & \color{DC143C}{\fbox{1}} & \color{318CE7}{0} & \color{318CE7}{2} \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} \color{DC143C}{x_1}\\\color{DC143C}{x_3}\\\color{318CE7}{x_2}\\\color{318CE7}{x_4} \\ \end{bmatrix} =0

Now you can see RR as:

R′=[IF00]R'=\begin{bmatrix} \color{DC143C}{\text{I}} & \color{318CE7}{\text{F}} \\ 0 & 0 \\ \end{bmatrix}

Remember that number of special solution is 2\color{318CE7}{2} because we have 2 free column vectors.
So we know that there are 2\color{318CE7}{2} special solution possible.

Say that special solutions are:

x⃗(1)=[x1(1)x2(1)x3(1)x4(1)] and x⃗(2)=[x1(2)x2(2)x3(2)x4(2)]\vec{x}^{(1)}=\begin{bmatrix} \color{DC143C}{x^{(1)}_1}\\\color{318CE7}{x^{(1)}_2}\\\color{DC143C}{x^{(1)}_3}\\\color{318CE7}{x^{(1)}_4}\\ \end{bmatrix} \text{ and } \vec{x}^{(2)}=\begin{bmatrix} \color{DC143C}{x^{(2)}_1}\\\color{318CE7}{x^{(2)}_2}\\\color{DC143C}{x^{(2)}_3}\\\color{318CE7}{x^{(2)}_4}\\ \end{bmatrix}

Now rearrange then,

x⃗′(1)=[x1(1)x3(1)x2(1)x4(1)] and x⃗′(2)=[x1(2)x3(2)x2(2)x4(2)]\vec{x}'^{(1)}=\begin{bmatrix} \color{DC143C}{x^{(1)}_1}\\\color{DC143C}{x^{(1)}_3}\\\color{318CE7}{x^{(1)}_2}\\\color{318CE7}{x^{(1)}_4}\\ \end{bmatrix} \text{ and } \vec{x}'^{(2)}=\begin{bmatrix} \color{DC143C}{x^{(2)}_1}\\\color{DC143C}{x^{(2)}_3}\\\color{318CE7}{x^{(2)}_2}\\\color{318CE7}{x^{(2)}_4}\\ \end{bmatrix}

Now stack then in a matrix say (NN)

N=[x1(1)x1(2)x3(1)x3(2)x2(1)x2(2)x4(1)x4(2)]N=\begin{bmatrix} \color{DC143C}{x^{(1)}_1} & \color{DC143C}{x^{(2)}_1} \\ \color{DC143C}{x^{(1)}_3} & \color{DC143C}{x^{(2)}_3} \\ \color{318CE7}{x^{(1)}_2} & \color{318CE7}{x^{(2)}_2} \\ \color{318CE7}{x^{(1)}_4} & \color{318CE7}{x^{(2)}_4} \\ \end{bmatrix}

and say

xpivot=[x1(1)x1(2)x3(1)x3(2)]; xfree=[x2(1)x2(2)x4(1)x4(2)]x_{\text{pivot}}=\begin{bmatrix} \color{DC143C}{x^{(1)}_1} & \color{DC143C}{x^{(2)}_1} \\ \color{DC143C}{x^{(1)}_3} & \color{DC143C}{x^{(2)}_3} \\ \end{bmatrix};\ x_{\text{free}} =\begin{bmatrix} \color{318CE7}{x^{(1)}_2} & \color{318CE7}{x^{(2)}_2} \\ \color{318CE7}{x^{(1)}_4} & \color{318CE7}{x^{(2)}_4} \\ \end{bmatrix}

And we are free to choose free variables so let xfree=[1001]x_{\text{free}} =\begin{bmatrix} \color{318CE7}{1} & \color{318CE7}{0} \\ \color{318CE7}{0} & \color{318CE7}{1} \\ \end{bmatrix}
Now N=[xpivotI2×2]N=\begin{bmatrix} \color{DC143C}{x_\text{pivot}}\\\color{318CE7}{I_{2\times2}} \end{bmatrix}

We want Rx⃗(1)=0R\vec{x}^{(1)}=0 and Rx⃗(2)=0R\vec{x}^{(2)}=0

⇒R′x⃗′(1)=0\Rightarrow R'\vec{x}'^{(1)}=0 and R′x⃗′(2)=0R'\vec{x}'^{(2)}=0
⇒R′N=0\Rightarrow R'N=0
So R′N=[I2×2F00][xpivotI2×2]=0R'N=\begin{bmatrix} \color{DC143C}{I_{2\times2}} & \color{318CE7}{\text{F}} \\ 0 & 0 \\ \end{bmatrix} \begin{bmatrix} \color{DC143C}{x_\text{pivot}}\\\color{318CE7}{I_{2\times2}} \end{bmatrix} = 0
⇒xpivotI2×2+FI2×2=0\Rightarrow \color{DC143C}{x_\text{pivot}} \color{DC143C}{I_{2\times2}} + \color{318CE7}{\text{F}} \color{318CE7}{I_{2\times2}} =0
⇒xpivot=−F\Rightarrow \color{DC143C}{x_\text{pivot}} = - \color{318CE7}{\text{F}}

So N=[FI2×2]N=\begin{bmatrix} \color{318CE7}{\text{F}} \\ \color{318CE7}{I_{2\times2}}\\ \end{bmatrix}

And we know that F=[2−202]\color{318CE7}{ F=\begin{bmatrix} 2&-2\\0&2\\ \end{bmatrix} }

So N=[−220−21001]N=\begin{bmatrix} \color{DC143C}{-2} & \color{DC143C}{2} \\ \color{DC143C}{0} & \color{DC143C}{-2} \\ \color{318CE7}{1} & \color{318CE7}{0} \\ \color{318CE7}{0} & \color{318CE7}{1} \\ \end{bmatrix}

⇒x⃗′(1)=[x1(1)x3(1)x2(1)x4(1)]=[−2010] and  x⃗′(2)=[x1(2)x3(2)x2(2)x4(2)]=[2−201]\Rightarrow \vec{x}'^{(1)}=\begin{bmatrix} \color{DC143C}{x^{(1)}_1}\\\color{DC143C}{x^{(1)}_3}\\\color{318CE7}{x^{(1)}_2}\\\color{318CE7}{x^{(1)}_4}\\ \end{bmatrix} = \begin{bmatrix} \color{DC143C}{-2}\\\color{DC143C}{0}\\\color{318CE7}{1}\\\color{318CE7}{0}\\ \end{bmatrix} \text{ and } \ \vec{x}'^{(2)}=\begin{bmatrix} \color{DC143C}{x^{(2)}_1}\\\color{DC143C}{x^{(2)}_3}\\\color{318CE7}{x^{(2)}_2}\\\color{318CE7}{x^{(2)}_4}\\ \end{bmatrix} = \begin{bmatrix} \color{DC143C}{2}\\\color{DC143C}{-2}\\\color{318CE7}{0}\\\color{318CE7}{1}\\ \end{bmatrix}
⇒x⃗(1)=[x1(1)x2(1)x3(1)x4(1)]=[−2100] and  x⃗(2)=[x1(2)x2(2)x3(2)x4(2)]=[20−21]\Rightarrow\vec{x}^{(1)}=\begin{bmatrix} \color{DC143C}{x^{(1)}_1}\\\color{318CE7}{x^{(1)}_2}\\\color{DC143C}{x^{(1)}_3}\\\color{318CE7}{x^{(1)}_4}\\ \end{bmatrix} = \begin{bmatrix} \color{DC143C}{-2}\\\color{DC143C}{1}\\\color{318CE7}{0}\\\color{318CE7}{0}\\ \end{bmatrix} \text{ and } \ \vec{x}^{(2)}=\begin{bmatrix} \color{DC143C}{x^{(2)}_1}\\\color{318CE7}{x^{(2)}_2}\\\color{DC143C}{x^{(2)}_3}\\\color{318CE7}{x^{(2)}_4}\\ \end{bmatrix} = \begin{bmatrix} \color{DC143C}{2}\\\color{DC143C}{0}\\\color{318CE7}{-2}\\\color{318CE7}{1}\\ \end{bmatrix}

So our Null space is space of all x⃗\vec{x} that are linear combinations of [−2100]\begin{bmatrix} -2\\1\\0\\0\\ \end{bmatrix} and [20−21]\begin{bmatrix} 2\\0\\-2\\1\\ \end{bmatrix}

x=α[−2100]+β[20−21];α,β∈Rx=\alpha \begin{bmatrix} -2\\1\\0\\0\\ \end{bmatrix} + \beta \begin{bmatrix} 2\\0\\-2\\1\\ \end{bmatrix};\quad \alpha,\beta\in\mathbb{R}