# Solving Ax = 0

  
This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).


```python
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits import mplot3d
import sympy
```

## Main idea

Let $A$ be an $m\times n$ matrix.  The solution set of $A{\bf x} = {\bf 0}$ is the intersection of the hyperplanes $\langle {\bf r}_i, {\bf x}\rangle = 0$ for all $i=1,\ldots,m$, where ${\bf r}_i$ is the $i$-th row of $A$.  
Therefore, the solution set of $A$ is a space and we call it the **kernel** $\operatorname{ker}(A)$ of $A$.

Every matrix lead to its **reduced echelon form** after some **row operations**.  If $R$ is the reduced echelon form of $A$, then $A{\bf x} = {\bf 0} \iff R{\bf x} = {\bf 0}$.

## Side stories

- row operations, reduced echelon form
- SymPy
- trivial or infinite solutions
- kernel (null space)
- row space
- rank + nullity = number of columns

## Experiments

###### Exercise 1
This exercise shows you that the kernel and the row space of a matrix are orthogonal to each other.  
Let  
```python
A = np.array([[1,1,1], 
              [1,1,1]])
```
The **nullity** of $A$ is the dimension of its kernel.  
The **rank** of $A$ is the dimension of its row space.  

###### 1(a)
Use the techniques you learned in Lesson 2 to draw some random points in the kernel of $A$.  
What is the nullity of $A$?


```python
### your answer here
```

###### 1(b)
Use the techniques you learned in Lesson 3 to draw a grid using the rows of $A$.  
What is the rank of $A$?


```python
### your answer here
```

###### 1(c)
Do the same for  
```python
B = np.array([[1,-1,0], 
              [1,0,-1]])
```
What is the nullity and the rank of $B$?


```python
### your answer here
```

## Exercises

##### Exercise 2
We need to rely on SymPy to do the row operations.  
You may use `sympy.Matrix(arr)` and `np.array(mtx, dtype=float)` to switch between two data types.  
Let
```python
A = sympy.Matrix([[1,1,1,1], 
                  [1,2,2,2], 
                  [1,2,2,3]])
R,pvts = A.rref()
```
Convince your self that $A$ and $R$ have the same kernel.


```python
### your answer here
```

##### Exercise 3
The function `A.rref()` returns the reduced echelon form of $A$ and the indices of the **pivots** --- they are the indices of the first one in each row.  
Find a $3\times 5$ matrix whose pivots are `(1,2,4)` .


```python
### your answer here
```

##### Exercise 4
Let  
```python
A = sympy.Matrix([[1,0,2,0,4], 
                  [0,1,3,0,5], 
                  [0,0,0,1,6]])
```
Then $A{\bf x} = {\bf 0}$ is equivalent to 
$$\begin{array}{rrrrrl}
x_0 & ~ & +2x_2 & ~ & +4x_4 & = 0 \\
~ & x_1 & +3x_2 & ~ & +5x_4 & = 0 \\
~ & ~ & ~ & x_3 & +6x_4 & = 0.
\end{array}$$

###### 4(a)
Suppose $x_2 = 1$ and $x_4 = 0$.  Solve the equation by hand.    
Use  
```python
x = sympy.Matrix([x0, x1, x2, x3, x4])
A * x
```
to check your answer.


```python
### your answer here
```

###### 4(b)
Find more solutions by setting $x_2 = s$ and $x_4 = t$.  
Let  
```python
h1,h2 = A.nullspace()
```
Is your answer the same as $s{\bf h}_1 + t{\bf h}_2$?  


```python
### your answer here
```

###### 4(c)
Here is the code for generating ${\bf h}$'s.  
Play with the code and understand the fancy indexing feature in NumPy.
```python
R,pvts = A.rref()

num_cols = A.shape[1]
rank = len(pvts)

R = np.array(R)
pvts = np.array(pvts)
frees = np.array([j for j in range(num_cols) if j not in pvts])

for j in frees:
    h = np.zeros((num_cols,))
    h[j] = 1
    h[pvts] = -R[:rank, j]
    print(h)
```


```python
### your answer here
```

##### 4(d)
Alternatively, you may generate a "null matrix" at once.  
Play with the code and understand the slicing feature in NumPy.
```python
R,pvts = A.rref()

num_cols = A.shape[1]
rank = len(pvts)

R = np.array(R)
pvts = np.array(pvts)
frees = np.array([j for j in range(num_cols) if j not in pvts])

num_frees = frees.shape[0]
hs = np.zeros((num_frees, num_cols))
hs[:, frees] = np.eye(num_frees)
hs[:, pvts] = -R[:rank, frees].T
```


```python
### your answer here
```

#### Remark
Let $R$ is a reduced echelon form.  
(Think of Exercise 4.)
The first one in each row = first variable in each equation = a leading variable. (e.g., `(0,1,3)` )  
Other variables = free variables.  (e.g., `(2,4)` )  
By assigning arbitrary numbers to free variables, one may solve the leading variables.  

rank = number of leading variables = number of nonzero rows in $R$  
nullity = number of free variables  

nullity = 0 $\iff$ $\operatorname{ker}(A)$ contains only one trivial ${\bf 0}$  
nullity > 0 $iff$ $\operatorname{ker}(A)$ has infinit solution

#### Dimension theorem
For any $m\times n$ matrix $A$,  
$$\operatorname{rank}(A) + \operatorname{nullity}(A) = n.$$

##### Exercise 5
Let  
```python
A = sympy.Matrix([[1,3,3,18], 
                  [5,15,16,95], 
                  [-5,-15,-15,-90]])
R,pvts = A.rref()
```
Use the same technique as Exercise 4 to solve the kernel of $A$.  
Then verify your answer by `A.nullspace()`.


```python
### your answer here
```

##### Exercise 6
Let  
```python
A = np.array([[1,1,1], 
              [1,1,1]])
A_sym = sympy.Matrix(A)
```
Use the vectors in `A_sym.nullspace()` to draw the grid.  
Check if the space is the same as what you did in Exercise 1.


```python
### your answer here
```

##### Exercise 7
Let  
```python
A = sympy.Matrix([[1,-1,0], 
                 [1,0,-1]])
R,pvts = A.rref()
```
Draw the grid in red using the rows of $A$ and draw the grid in blue using the rows of $R$.  
Are they the same space?



```python
### your answer here
```

2d745afd7eabd277adc8193e8643917416a71b66
ipynb
Jupyter Notebook
Mathematics/Linear Algebra/0.0b Supplement of MIT Course - Concept Explanations with Problems_and_Questions to Solve/05-Solving-Ax-=-0.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
Mathematics/Linear Algebra/0.0b Supplement of MIT Course - Concept Explanations with Problems_and_Questions to Solve/05-Solving-Ax-=-0.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
Mathematics/Linear Algebra/0.0b Supplement of MIT Course - Concept Explanations with Problems_and_Questions to Solve/05-Solving-Ax-=-0.ipynb
okara83/Becoming-a-Data-Scientist
f09a15f7f239b96b77a2f080c403b2f3e95c9650
MIT
2022-02-09T15:41:33.000Z
2022-02-11T07:47:40.000Z
Qwen/Qwen-72B
1. YES
2. YES