# Solving Ax = b

  
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 b}$ is the intersection of the affine planes $\langle {\bf r}_i, {\bf x}\rangle = b_i$ for all $i=1,\ldots,m$, where ${\bf r}_i$ is the $i$-th row of $A$ and $b_i$ is the $i$-th entry of ${\bf b}$.  
Therefore, the solution set of $A$ is an affine space (shifted space).

The solutions set of $A{\bf x} = {\bf b}$ is of the form:

    general solutions = particular solution + homogeneous solutions
    (a shifted space)      (a vector)              (a space)
   
Here "general solution" stands for all solutions of $A{\bf x} = {\bf b}$,  
"particular solution" stands for one arbitrary solution of $A{\bf x} = {\bf b}$, and  
"homogeneous solutions" stands for all solutions of $A{\bf x} = {\bf 0}$.

Every matrix lead to its **reduced echelon form** after some **row operations**.  If $\left[\begin{array}{cc}R | {\bf r}\end{array}\right]$ is the reduced echelon form of $\left[\begin{array}{cc}A | {\bf b}\end{array}\right]$, then $A{\bf x} = {\bf b} = R{\bf x} = {\bf r}$.

## Side stories

- $A{\bf x} = {\bf b} \iff {\bf b}\in\operatorname{Col}(A)$
- matrix inverse

## Experiments

###### Exercise 1
This exercise helps you to visualize the affine space $A{\bf x} = {\bf b}$.  
Let  
```python
A = np.array([[1,1,1], 
              [1,1,1]])
b = np.array([5,5])
```

###### 1(a)
Use the techniques you learned in Lesson 2 to draw some random solutions of $A{\bf x} = {\bf b}$.  
What is the nullity of $A$?  What is the "dimension" of the affine space?  
Hint:  
```python
xs = 5*np.random.randn(3,10000)
mask = (np.abs(b[:,np.newaxis] - A.dot(xs)) < 0.1).all(axis = 0)
```


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

###### 1(b)
It is known that  
```python
p = np.array([5,0,0])
```
is a particular solution of $A{\bf x} = {\bf b}$.  
Add a vector of `p` upon your previous drawing.


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

###### 1(c)
Do the same for  
```python
b = np.array([5,6])
```
How many solutions are there?


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

###### Exercise 2
This exercise helps you to visualize the affine space $A{\bf x} = {\bf b}$.  
Let  
```python
A = np.array([[1,1,1], 
              [1,1,1]])
b = np.array([5,5])
```

###### 2(a)
Draw the grid using the columns of $A$ and draw a vector for $b$.  
Is $b$ in the column space of $A$?


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

###### 2(b)
Do the same for 
```python
b = np.array([5,6])
```
Is $b$ in the column space of $A$?


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

#### Remark  
Whether a particular solution exists depends only on whether ${\bf b}$ is in the column space of $A$ or not.  
We say a equation $A{\bf x} = {\bf b}$ is **consistent** if it has at least a particular solution.  

Whether the homogeneous solutions contains only the trivial solution ${\bf 0}$ depends only on $A$.  

This table summarize the number of solutions of $A{\bf x} = {\bf b}$.

 hom \ par | consistent | inconsistent 
 --------- | ---------- | ------------ 
 trivial | one | none 
 nontrivial | infinite | none


## Exercises

##### Exercise 3
Let  
```python
A = sympy.Matrix([[1,1], 
                  [-1,0],
                  [0,-1]])
b = sympy.Matrix([3,-2,-1])
Ab = A.col_insert(2,b)
```

###### 3(a)
Calculate the reduced echelon form of `Ab` .  
Can you tell if  `b` is in the column space of `A` ?


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

###### 3(b)
Let  
```python
b = sympy.Matrix([1,2,3])
```
and update `Ab` .  
Can you tell if `b` is in the column space of `A` ?


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

##### Exercise 4
Let  
```python
A = sympy.Matrix([[1,1,1], 
                  [1,2,4], 
                  [1,3,9]])
b1 = sympy.Matrix([1,0,0])
```

###### 4(a)
If a matrix has no free variable, then the homogeneous solution is trivial.  
Find the unique solution of $A{\bf x} = {\bf b}_1$.


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

###### 4(b)
Let  
```python
b2 = sympy.Matrix([0,1,0])
Ab = A.col_insert(3,b1)
Abb = Ab.col_insert(4,b2)
```
Can you use `Abb` to solve the solutions of $A{\bf x} = {\bf b}_1$ and $A{\bf x} = {\bf b}_2$ at once?


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

###### 4(c)
Let  
```python
b3 = sympy.Matrix([0,0,1])
```  
Solve the solutions of $A{\bf x} = {\bf b}_1$,  $A{\bf x} = {\bf b}_2$, and $A{\bf x} = {\bf b}_3$ at once.


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

###### 4(d)
Let  
$$ B = \begin{bmatrix} 
 | & ~ & | \\
 {\bf b}_1 & \cdots & {\bf b}_3 \\
 | & ~ & | 
 \end{bmatrix}.$$
 Find a matrix $X$ such that $AX = B$.  
 When $B$ is the identity matrix  
$$ I_n = \begin{bmatrix} 
 1 & ~ & ~ \\
 ~ & \ddots & ~ \\
 ~ & ~ & 1 
 \end{bmatrix},$$
 the matrix $X$ with $AX = I_n$ is called the **inverse** of $A$, denoted by $A^{-1}$.


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

###### 4(e)
Compare your answer in 4(d) with the output of `np.linalg.inv(A)` .


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

##### Exercise 5
Let  
```python
A = sympy.Matrix([[1,3,3,18], 
                  [5,15,16,95], 
                   [-5,-15,-15,-90]])
R,pvts = A.rref()
```

###### 5(a)
Let $B$ be the matrix whose columns are the columns of $A$ the corresponding to leading variables.  
Pick a column of $A$ corresponding a free variable.  
Check that the column is in the column space of $B$.  
(If yes, this means this column is redundant for generating the column space of $A$.)


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

###### 5(b)
Check if $B$ itself has any redundant column.


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

#### Remark
Let $S = \{{\bf u}_1, \ldots, {\bf u}_n\}$ be a collection of vectors and $A$ the matrix whose columns are $S$.  
We say $S$ is **linearly independent** if one of the following equivalent condition holds:
- $c_1{\bf u}_1 + \cdots + c_n{\bf u}_n = {\bf 0}$ only have trivial solution $c_1 = \cdots = c_n = 0$.
- $A{\bf x} = {\bf 0}$ only have trivial solution ${\bf x} = 0$.
- $A$ has no free variable.

Moreover, if a space $V$ is equal to$\operatorname{span}(S)$ and $S$ is linearly independent, then we say $S$ is a **basis** of the the space $V$.

##### Exercise 6
Let  
```python
A = sympy.Matrix([[1,1,1], 
                  [-1,0,0],
                  [0,-1,0],
                  [0,0,-1]])
```
Check if the columns of $A$ form a linearly independent set.


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

##### Exercise 7
```python
A = sympy.Matrix([[1,3,3,18], 
                  [5,15,16,95], 
                  [-5,-15,-15,-90]])
R,pvts = A.rref()
```
Check what is `A.nullspace()`, `A.rowspace()`, and `A.columnspace()` and think about their meaning.  


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

#### Remark
Since it is impossible to output a space, the three commands in Exercise 7 in fact outputs the basis of the space only, which is enough.

**Nullspace**: its basis consists of ${\bf h}$'s in the previous lesson.  
**Rowspace**: its basis consists of the rows of $R$ corresponding to the pivots.  
**Columnspace**: its basis consists of the columns of $A$ corresponding to the pivots.

5529cb4444076f3c228ec440e39a24ddd9326f12
ipynb
Jupyter Notebook
Mathematics/Linear Algebra/0.0b Supplement of MIT Course - Concept Explanations with Problems_and_Questions to Solve/06-Solving-Ax-=-b.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/06-Solving-Ax-=-b.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/06-Solving-Ax-=-b.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