Solving Ax=b

From bio-physics-wiki

Jump to: navigation, search

We already solved for the equation $\mathbf{Ax}=\mathbf{b}$ for the special RHS $\mathbf{b}=\mathbf{0}$ to find the vectors in the Nullspace. Now we would like to find out how to solve for general $\mathbf{b}$'s on the RHS. The question arises, if there is a solution for every $\mathbf{b}$, of if there are some $\mathbf{b}$'s for which we can find no solution (solvability). \begin{align} \begin{bmatrix} 1 & 2 & 2 &2\\ 2 & 4 &6 &8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3\\ x_4 \end{bmatrix}&= \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix} \end{align} As we learned in the article on Matrix Elimination, we can augment $\mathbf{b}$ to matrix $\mathbf{A}$ and start elimination. \begin{align} \begin{array}{rrrr|r} 1 & 2 & 2 &2 &b_1\\ 2 & 4 &6 &8 &b_2\\ 3 & 6 & 8 & 10 &b_3\end{array} \rightarrow \begin{array}{rrrr|r} 1 & 2 & 2 &2 &b_1\\ 0 & 0 &2 &4 &b_2-2b_1\\ 0 & 0 & 2 & 4 &b_3-3b_1\end{array} \rightarrow \begin{array}{rrrr|r} 1 & 2 & 2 &2 &b_1\\ 0 & 0 &2 &4 &b_2-2b_1\\ 0 & 0 & 0 & 0 &b_3-b_2-b_1\end{array} \end{align} We find the condition $b_3-b_2-b_1=0$ for solvability. If we choose $b_1=1$ and $b_2=5$, then $b_3$ must be $b_3=6$ to satisfy $b_3-b_2-b_1=0$. If we think in terms of the column space, then the equation is solvable, if $\mathbf{b}$ is an element of the column space of $\mathbf{A}$. In the row picture, the requirement is, that a combination of rows must be zero, to get solutions.


Find the Complete Solution to Ax=b

The complete solution to $\mathbf{Ax}=\mathbf{b}$ consists of the particular or complementary solution and the special solution (Nullspace solutions). Find the complete solution for the above example with $\mathbf{b}=(1,3,4)$

  • Find the particular solution: set all free variables (red) to zero and solve for the pivot variables.

\begin{align} \begin{array}{rrrr|r} 1 & \color{red}{2} & 2 &\color{red}{2} &b_1\\ 0 & 0 &2 & \color{red}{4} &b_2-2b_1\\ 0 & 0 & 0 & 0 &b_3-b_2-b_1\end{array} \end{align} \begin{align} x_1 + 2x_3 = 1\\ 2x_3=3 \end{align}

so the particluar solution is $\mathbf{x}_p=(-2,0,3/2,0)$

\begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3\\ x_4 \end{bmatrix}&= c \cdot \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} \end{align} \begin{align} \begin{bmatrix} x_1 \\ x_2 \\ x_3\\ x_4 \end{bmatrix}&= d \cdot \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} \end{align}

so the general special solution is given by all linear combinations of these solutions

\begin{align} \mathbf{x}_n&= c \cdot \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d \cdot \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} \end{align}


  • The complete solution is given by both

\begin{align} \mathbf{Ax}_p=\mathbf{b} \end{align}

and

\begin{align} \mathbf{Ax}_n=\mathbf{0} \end{align}

because we can always add the solution $\mathbf{x}_n$ to $\mathbf{x}_p$ and still get $\mathbf{b}$ on the RHS.

\begin{align} \mathbf{A}(\mathbf{x}_n+\mathbf{x}_p)=\mathbf{0}+\mathbf{b} \end{align}

The complete solution is

\begin{align} \mathbf{x}=\mathbf{x}_n+\mathbf{x}_p= \begin{bmatrix} -2 \\ 0 \\ 3/2 \\ 0 \end{bmatrix} + c \cdot \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d \cdot \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} \end{align}


Four Cases

For rank $r$, $m$ rows and $n$ columns we distinguish matrices

  • $r=m=n$ full rank square matrix, then the reduced row echelon form $\mathbf{R}$ is the identity matrix

\begin{align} \mathbf{R}=\mathbf{I} \end{align} and we can find one unique solution.

  • $r=n<m$ there are more rows than columns. The system is over determined and there is ether one unique solution or no solution, if $\mathbf{b}$ isn't in the column space of $\mathbf{A}$. The reduced row echelon form $\mathbf{R}$ will be of the form

\begin{align} \mathbf{R}=\begin{bmatrix} \mathbf{I} \\ \mathbf{0} \end{bmatrix} \end{align}

  • $r=m<n$ there are more columns than rows. The system is under determined and there are infinitely many solutions (from the Nullspace). The reduced row echelon form $\mathbf{R}$ will be of the form

\begin{align} \mathbf{R}=\begin{bmatrix} \mathbf{I} & \mathbf{F} \end{bmatrix} \end{align}

  • $r<m$ and $r<n$ there exist ether zero or infinitely many solutions. The reduced row echelon form is

\begin{align} \mathbf{R}=\begin{bmatrix} \mathbf{I} & \mathbf{F} \\ \mathbf{0} & \mathbf{0} \end{bmatrix} \end{align}









Video Lectures:

  • Gilbert Strang - Introduction to Linear Algebra Lec. 7
  • Gilbert Strang - Introduction to Linear Algebra Lec. 8