# ML Wiki

## Homogeneous Linear Systems $A\mathbf x = \mathbf 0$

Suppose we have a system $A\mathbf x = \mathbf 0$. Such a system is called homogeneous - because we have $\mathbf 0$ on the right side of the system.

## Solving $A\mathbf x = \mathbf 0$

How to solve such a system?

• The solutions to this system form Nullspace $N(A)$
• we can solve it with Gaussian Elimination. The elimination doesn't change $N(A)$ - the solutions remain the same if we linearly combine the rows
• but note that the elimination changes the Column Space $C(A)$ of $A$

### Elimination and Echelon Form

Suppose we have a matrix $A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \\ \end{bmatrix}$

• note that row 3 is a linear combination of row 1 and row 2 (the system is not linearly independent)
• while doing the elimination we'll notice it

Let's do it:

• $\begin{bmatrix} \boxed 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \\ \end{bmatrix} \to \begin{bmatrix} \boxed 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \\ \end{bmatrix}$
• we have 0's in the second column, but in the next column there's a non-zero value - can take it as a pivot!
• $\begin{bmatrix} \boxed 1 & 2 & 2 & 2 \\ 0 & 0 & \boxed 2 & 4 \\ 0 & 0 & 2 & 4 \\ \end{bmatrix} \to \begin{bmatrix} \boxed 1 & 2 & 2 & 2 \\ 0 & 0 & \boxed 2 & 4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} = U$
• it's not really an upper-triangular matrix, but we still can call it $U$
• this $U$ is in the echelon form (or "staircase" form)

rank $r$ of a matrix is the number of Pivot variables in the echelon form

During the elimination the nullspace $N(A)$ of $A$ doesn't change

• so systems $A\mathbf x = \mathbf 0$ and $U \mathbf x = \mathbf 0$ have the same solutions $\mathbf x$
• the column with pivot variables are called pivot columns, there are $r$ of them
• the rest of the columns are called free columns, there are $n - r$ of them

Now let's try to solve this system $\left\{\begin{array}{rl} x_1 + 2 x_2 + 2 x_3 + 2 x_4 & = 0 \\ 2 x_3 + 4 x_4 & = 0 \\ \end{array}\right.$

We can find some solutions for pivot variables, but what to do with the free ones?

• They can have any value
• So we may assign something to them and then solve the system with backsubstitution for the pivot variables
• E.g. let's assign 1 and 0 to $x_2$ and $x_4$
• we have $\mathbb x = \begin{bmatrix} x_1 \\ 1 \\ x_3 \\ 0 \end{bmatrix}$, then we solve the system and get $\mathbb x = \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}$
• we can also take any linear combination of this solution, so we should write $\mathbb x = c_1 \cdot \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}$
• what if we assign different values to $x_2$ and $x_4$?
• Can assign this way: $\mathbb x = \begin{bmatrix} x_1 \\ 0 \\ x_3 \\ 1 \end{bmatrix}$, then we solve and get $\mathbb x = \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$
• so we have another "special" solution $\mathbb x = c_2 \cdot \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$
• so the final solution to this system will be
• $\mathbf x = c_1 \cdot \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + c_2 \cdot \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$
• this is the Nullspace $N(A)$ of the matrix $A$

### Row Reduced Echelon Form

Can we do simpler?

Suppose we have matrix $A$ that we reduced to $U = \begin{bmatrix} \boxed 1 & 2 & 2 & 2 \\ 0 & 0 & \boxed 2 & 4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}$

• can we clean it further? Can try to clean the pivot columns upwards - so there's only one 1 and the rest are 0's
• $U = \begin{bmatrix} \boxed 1 & 2 & 2 & 2 \\ 0 & 0 & \boxed 2 & 4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} \to \begin{bmatrix} \boxed 1 & 2 & 0 & -2 \\ 0 & 0 & \boxed 1 & 4 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} = R$
• $R$ is a Row Reduced Echelon Form (RRFR) of $A$
• note that if we consider only the pivot rows and columns, we see that we have the identity matrix $\begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}$

So now if we take a look at our new system, we have

• $\left\{\begin{array}{rl} x_1 + 2 x_2 - 2 x_4 & = 0 \\ x_3 + 2 x_4 & = 0 \\ \end{array}\right.$
• $A \mathbf x = \mathbf 0$, $U \mathbf x = \mathbf 0$ and $R \mathbf x = \mathbf 0$ - all have the same solutions $\mathbf x$!

Let's rearrange columns in $R$ so first we have the pivot columns, and then the free columns

• $\begin{bmatrix} 1 & 0 & 2 & -2 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}$
• now can distinguish the $I$ part (identity) and the $F$ part (free)
• these $I$ and $F$ appear in the "special" solutions of the $U \mathbf x = \mathbf 0$!
• only $F$ comes with the minus sign:

Why does it happen?

• assume we have a RREF $R = \begin{bmatrix} I & F \\ 0 & 0 \\ \end{bmatrix}$
• we have $r$ pivot columns, $n-r$ free columns and $r$ pivot rows
• we want to solve $R\mathbf x = \mathbf 0$. What are the "special" solutions?
• let's create a Nullspace matrix $N$, $N = \begin{bmatrix} -F \\ I \end{bmatrix}$
• Columns of $N$ are our special solutions
• let's take a closer look at one of these columns $\begin{bmatrix} \mathop{\mathbf x_\text{pivot}}\limits_{|}^{|} \\ \mathop{\mathbf x_\text{free}}\limits_{|}^{|} \\ \end{bmatrix}$. The system is $\begin{bmatrix} I & F \\ 0 & 0 \\ \end{bmatrix} \cdot \begin{bmatrix} \mathop{\mathbf x_\text{pivot}}\limits_{|}^{|} \\ \mathop{\mathbf x_\text{free}}\limits_{|}^{|} \\ \end{bmatrix} = \mathbf 0$
• $\Rightarrow I x_\text{pivot} + F x_\text{free} = \mathbf 0$ or $x_\text{pivot} = - F x_\text{free}$
• where for $x_\text{free}$ we use "special" choices $\mathbf e_1, \mathbf e_2, ...$ (columns of $I$)