Algorithm for solving $Ax=0$-Amit Rajan Blog

5.1 Algorithm for solving $Ax=0$

The idea behind this exercise is to come up with an algorithm to find the nullspace of a matrix $A$ . Let us start by taking a matrix $A$ .

$\begin{align} A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \end{align}$

One of the first thing to notice in $A$ is that $row_3$ is a linear combination of $row_1$ and $row_2$ ( $row_3 = row_1 + row_2$ ). The way to solve a system of linear equations is by elimination. Different row elimination steps can be used to transform $A$ into an upper triangular matrix with the same steps repeated on the right hand side. As the right hand side is $0$ here, the elimination steps can be skipped for it.

$\begin{align} A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \xrightarrow{\text{S1}} \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \end{bmatrix} \xrightarrow{\text{S3}} \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} = U \end{align}$

The resultant matrix after the elimination steps is $U$ which is in the echelon form. Now, instead of solving $Ax=0$ , $Ux=0$ can be solved. There are two pivots: $U_{11} = 1,U_{23} = 2$ . The number of pivots is also called as the rank of the matrix. Here, the rank is $2$ . The columns in which pivots are there ( $col_1, col_3$ ) are called as pivot columns. Remaining columns ( $col_2, col_4$ ) are called as free columns. The equation $Ux=0$ can be written as follows.

$\begin{align} x_1\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} + x_2\begin{bmatrix} 2 \\ 0 \\ 0 \end{bmatrix} + x_3\begin{bmatrix} 2 \\ 2 \\ 0 \end{bmatrix} + x_4\begin{bmatrix} 2 \\ 4 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \end{align}$

The values in $x$ corresponding to the free columns (here they are $x_2,x_4$ ) can be assigned any values and then we can find the values of $x_1,x_3$ to complete the solution. We can systematically assign values to the multipliers corresponding to the free columns. Let $x_2=1,x_4=0$ , this gives $x_1=-2,x_3=0$ and hence $\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}$ is a solution (or any multiple of this vector), a vector in the null space. Another choice for free variables can be $x_2=0,x_4=1$ , which gives $x_1=2,x_3=-2$ and hence $\begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$ is another solution (or any multiple of this vector), another vector in the null space. Hence, the general solution can be given as:

$\begin{align} x = c\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d\begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} \end{align}$

Another thing to note is the number of individual solutions is equal to the number of free variables or free columns. For a $m \times n$ matrix whose rank is $r$ , the number of free columns/variables( individual solutions) will be $n-r$ .

5.2 Reduced Row-Echelon Form

The row-echelon matrix $U$ can be further simplified by elimination steps. The idea is to get a matrix which have $0$ in the cells above and below pivot. Furthermore, the pivot values can be reduced to $1$ . The reduced matrix $R$ is called as the matrix in reduced row-echelon form.

$\begin{align} U = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} = R \end{align}$

If we further examine the matrix $R$ , it can be noticed that an identity matrix $\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = I$ sits in the pivot rows and columns ( $row_1, row_2, col_1, col_2$ ). Corresponding entries in the free columns are $\begin{bmatrix} 2 & -2 \\ 0 & 2 \end{bmatrix} = F$ . If we look at $I$ and $F$ , they are nothing but the rearranged individual solutions with sign switched for $F$ . Let us just rearrnage the reduced row-echelon matrix $R$ as follows, where the last matrix is nothing but matrix represented in the block form. We have to find $x$ such that $Rx=0$ .

$\begin{align} R = \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 2 & -2 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix} \end{align}$

For the given R in the block form, the solution can be given as:

$\begin{align} \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix}\begin{bmatrix} -F \\ I \end{bmatrix} = 0 \end{align}$

Hence, the final solution in the rearranged form is:

$\begin{align} \begin{bmatrix} -F \\ I \end{bmatrix} = \begin{bmatrix} -2 & 0 \\ 2 & -2 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \end{align}$

5.3 Example

Let us look at one more example. The system of equations which we have to solve is $Bx=0$ where $B=A^T$ for the above matrix $A$ .

$\begin{align} B = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 2 & 6 & 8 \\ 2 & 8 & 10 \end{bmatrix} \end{align}$

The transformation of $B$ into row-reduced echelon form can be given as follows:

$\begin{align} B = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 2 & 6 & 8 \\ 2 & 8 & 10 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 2 & 2 \\ 0 & 4 & 4 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 3 \\ 0 & 2 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 1 \\ 0 & 2 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix} \end{align}$

$\begin{align} I = \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}; F = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \end{align}$

Hence the null space can be given as

$\begin{align} c\begin{bmatrix} -F \\ I \end{bmatrix} = c\begin{bmatrix} -1 \\ -1 \\ 1 \end{bmatrix} \end{align}$

FEATURED TAGS

alternate-hypothesis applied basis basis-function bayes-theorem-for-gaussian-variables bernoulli-distribution binomial-distribution bishop cdf classification column-space conceptual confidence-intervals conjugate-prior cross-validation determinant dimension eigenvalue-decomposition eigenvalues eigenvectors exercises expectation-maximization exponential-distribution feed-forward-network gaussian-distribution gilbert-strang graphical-models hypothesis-testing islr kernel-methods lagrange-multipliers least-squares linear-algebra linear-equations linear-model-selection linear-models linear-regression logistic-regression matrix-factorization matrix-multiplications matrix-space maximum-likelihood-for-the-gaussian maximum-margin-classifiers mean mixture-models mixtures-of-gaussians moving-beyond-linearity multinomial-distribution neural-networks normal-distribution null-hypothesis null-space one-tailed-test pattern-recognition pmf power probability-distributions projection random-variables regularization resampling statistical-learning students-t-distribution subspace support-vector-machines support-vectors think-stats tree-based-methods two-tailed-test unsupervised-learning variance vector-space

5.1 Algorithm for solving Ax=0Ax=0

5.2 Reduced Row-Echelon Form

5.3 Example

CATALOG

FEATURED TAGS

5.1 Algorithm for solving $Ax=0$