{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

# How to find a basis of the kernel?

## Problem

Let

$$
A = \begin{bmatrix}
1 & -5 & -4 & -4 & 5 & 8 \\
-2 & 10 & 8 & 8 & -9 & -14 \\
-5 & 25 & 20 & 20 & -23 & -36 \\
-5 & 25 & 20 & 20 & -23 & -36
\end{bmatrix}\text{ and }
R = \begin{bmatrix}
1 & -5 & -4 & -4 & 0 & -2 \\
0 & 0 & 0 & 0 & 1 & 2 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}.
$$

It is known that $R$ is the reduced echelon form of $A$. Find a basis for the kernel $\ker(A)$.

## Thought

According to the article "[How to solve a system of linear equations?](https://hackmd.io/@jephianlin/HkM6o-cAh)", the kernel of $A$ can be written as $\vspan(\{\bh_1, \ldots, \bh_k\})$ for some homogeneous solutions $\bh_i$'s, where $k$ is the number of free variables. Let $S = \{\bh_1, \ldots, \bh_k\}$. Then we have $\ker(A) = \vspan(S)$, which is one of the conditions for $S$ being a basis of $\ker(A)$. As long as we can show that $S$ is linearly independent, then $S$ is a basis of $\ker(A)$.

## Sample answer

By observing the reduced echelon form, we know the indices $2$, $3$, $4$, and $6$ correspond to the free variables. By setting one of them as $1$ and others as $0$, we get the set of homogeneous solutions

$$
\begin{aligned}
S &= \{\bh_1, \bh_2, \bh_3, \bh_4\} \\
&= \left\{
\begin{bmatrix} 5 \\ {\color{red}1} \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix},
\begin{bmatrix} 4 \\ 0 \\ {\color{red}1} \\ 0 \\ 0 \\ 0 \end{bmatrix},
\begin{bmatrix} 4 \\ 0 \\ 0 \\ {\color{red}1} \\ 0 \\ 0 \end{bmatrix},
\begin{bmatrix} 2 \\ 0 \\ 0 \\ 0 \\ -2 \\ {\color{red}1} \end{bmatrix}
\right\}.
\end{aligned}
$$

By the way we solve the solutions, we know $\ker(A) = \vspan(S)$. Now we may check the linearly independency of $S$. Suppose

$$
c_1\bh_1 + c_2\bh_2 + c_3\bh_3 + c_4\bh_4 = \bzero.
$$

By comparing the second entries on the both sides, we know $c_1 = 0$. Similarly, the equation on the third entries gives $c_2 = 0$. The fourth entries give $c_3 = 0$, and the sixth entries give $c_4 = 0$. Therefore, $S$ is linearly independent.

Combining all above results, we know $S$ is a basis of $\ker(A)$.

## Note

It turns out that by the way we found the homogeneous solutions, there is a "hidden identity matrix" in $S$. (Use the electronic version of this note to see the red part above.) Therefore, The set $S$ of homogeneous solutions is always linearly independent by our choice (why?).

This means the dimension of $\ker(A)$ is the number of free variables. This number is called the _nullity_ of $A$, denoted as $\nul(A)$.

Run the SageMath code below or simply click [here](https://sagecell.sagemath.org/?q=ewiqir). The code generates some random matrices. Use the code to do some practices by yourself, and then check your answer by modifying `print_ans` in the code.

load("https://raw.githubusercontent.com/jephianlin/LA-notebook/main/lingeo.py")

set_random_seed(None) # replace None with your favorite number
m,n,r = 4,6,2 # m x n matrix with rank r
A, R, pivots = random_good_matrix(m,n,r, return_answer=True)
pretty_print(LatexExpr("A="), A, LatexExpr("\\rightsquigarrow R="), R)

Kb = kernel_matrix(A)
Cb = column_space_matrix(A)
Rb = row_space_matrix(A)

print_ans = "No" # replace No with K, C, R, or All
if print_ans in ["K", "All"]:
    K_basis = [(Kb[:,i//2] if i % 2 == 0 else ",") for i in range(2*(n-r)-1)]
    pretty_print("a basis of ker(A) can be", LatexExpr("\\ \\Big\\{"), *K_basis, LatexExpr("\\Big\\}"))
if print_ans in ["C", "All"]:
    K_basis = [(Cb[:,i//2] if i % 2 == 0 else ",") for i in range(2*r-1)]
    pretty_print("a basis of Col(A) can be", LatexExpr("\\ \\Big\\{"), *K_basis, LatexExpr("\\Big\\}"))
if print_ans in ["R", "All"]:
    K_basis = [(Rb[i//2,:] if i % 2 == 0 else ",") for i in range(2*r-1)]
    pretty_print("a basis of Row(A) can be", LatexExpr("\\ \\Big\\{"), *K_basis, LatexExpr("\\Big\\}"))


*This note can be found at Course website > Learning resources.*