##### Tools

This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

# Solving systems of linear equations

Main topics:

• Gaussian elimination
• Solving systems of linear equations over ${\bf R}$
• Possible geometric structure of the solution set to a system of $3$ linear equations over ${\bf R}$ in $3$ unknowns
• Reduced row echelon form of a matrix is unique.
• Possible solution sets for a system of $3$ linear equations.

Planes in ${\bf R}^3$ are given by linear equations.

$$a_1^k\bar{x_1} + a_2^k\bar{x_2}+ \ldots + a_n^k\bar{x_n} = \bar{b_k}$$

This is "$k$ equations in $n$ unknowns$! There is a vector equation behind this system of linear (scalar) equations. Problem: Given all the coefficients and all the vectors$\bar{b_i}$, find the vectors$\bar{x_1},\ldots,\bar{x_n}$. Example:$\left\{ \begin{array}{rl} 3x+4y=9 \\ 5x+7y=2 \end{array} \right.$•$3x+4y=9$•$5x+7y=2$Our vector space is${\bf R}$,$x,y \in {\bf R}$. Now let's simplify the algebra: Idea: ignore the variables.$\begin{array}{} 3&4&9&R_1 \\ 5&7&2&R_2 \\ 8&11&11&R_1+R_2 \end{array}$This means$8x+11y=11$. Example: Solve$\left\{ \begin{array}{rl} x+z=5 \\ y+z=3 \\ 2x+z=8 \end{array} \right.$Superposition of waves:$\bar{w_1}+\bar{w_2}$Different scales: A linear equation looks like $$a_1^1\bar{x_1}+a_2^1\bar{x_2}+ \ldots + a_n^1\bar{x_n} = \bar{b_1}.$$ System of equations Example:$\left\{ \begin{array}{rl} 3x+4y=9 \\ 5x+7y=2 \end{array} \right.$Generally: $$a_1^1\bar{x_1} + a_2^1\bar{x_2}+\ldots+a_n^1\bar{x_n} = \bar{b_1}$$ $$a_1^2\bar{x_1} + a_2^2\bar{x_2}+\ldots+a_n^2\bar{x_n} = \bar{b_2}$$ • 1. Translate$\begin{array}{} 1 & 0 & 1 & 5 & R_1 \\ 0 & 1 & 1 & 3 & R_2 \\ 2 & 0 & 1 & 8 & R_3 \\ 0 & 0 & -1 & -2 & R_4=R_3-2R_1 \end{array}$• 2. Solve Means$-z=-2\begin{array}{} 0 & 0 & 1 & 2 & R_5=-R_4 \\ 1 & 0 & 0 & 3 & R_6=R_1-R_5 \\ \end{array}x=3\begin{array}{} 0 & 1 & 0 & 1 & R_7=R_2-R_5 \\ \end{array}y=1$• 3. Interpret the solution$x=3$,$y=1$,$z=2$Let's review. We've learned how to solve systems via augmented matrices. They look like this one:$\left[ \begin{array}{ccc|c} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 5 \end{array} \right]$The left side of the bar has the coefficients of$x_1$,$x_2$,$x_3$variables and the right side of the bar has the free terms. The line is important! It reminds you: augmented matrix is not a matrix. We solve them by means of appropriately recorded row operations. Plan:$\left[ \begin{array}{cc|c} \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \end{array} \right] \stackrel{{\rm row \hspace{3pt} op}}{\rightarrow} \left[ \begin{array}{cccc|c} 1 & 0 & 0 & 2 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 2 & 2 \end{array} \right]$Example: The result can be rewritten as the solution of the system...$\left\{ \begin{array}{} x_1 & & & +2x_4 &= 1 &\rightarrow & x_1 = 1-2x_4 \\ & x_2 & & +x_4 &= 0 &\rightarrow & x_2=-x_4 \\ & & x_3 & +2x_4 &= 2 &\rightarrow & x_3=2-2x_4 \end{array} \right.$Now what is the solution set$S \subset {\bf R}^4$, i.e., those$(x_1,x_2,x_3,x_4)$that satisfy the system? Idea: Make$x_4$a parameter,$t$. Then,$\left\{ \begin{array}{} x_1 &=1-2t \\ x_2 &=-t \\ x_3 &=2 - 2t\\ x_4 &=t \end{array} \right.$Rewrite in the vector form:$\left[ \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = \left[ \begin{array}{} 1-2t \\ -t \\ 2-2t \\ t \end{array} \right] = \left[ \begin{array}{} 1 \\ 0 \\ 2 \\ 0 \end{array} \right] + \left[ \begin{array}{} -2t \\ -t \\ -2t \\ t \end{array} \right] = \left[ \begin{array}{} 1 \\ 0 \\ 2 \\ 0 \end{array} \right] + t\left[ \begin{array}{} -2 \\ -2 \\ -2 \\ 1 \end{array} \right]$The vector on the left hand side is the vector$x$, solution, and the vectors on the right hand side are$a$and$v$respectively. In$t$,$a$and$v$are specific! Thus$x=a+tv$,$t \in {\bf R}$. So the solution set is$S = \{ x = a+tv \colon t \in {\bf R} \}$. By definition,$s$is a line: Example: Example of a plane as the solution set. $$S = \{x = a+tv+sw \colon t, s \in {\bf R} \} \subset {\bf R}^4$$ Definition.$a = \left[ \begin{array}{} 1 \\ 2 \\ 3 \\ 4 \end{array} \right]$,$v = \left[ \begin{array}{} 0 \\ 1 \\ 0 \\ 1 \end{array} \right]$,$w = \left[ \begin{array}{} 1 \\ 0 \\ 1 \\ 0 \end{array} \right]$Rewrite.$\left[ \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right] = \left[ \begin{array}{} 1 \\ 2 \\ 3 \\ 4 \end{array} \right] + t \left[ \begin{array}{} 0 \\ 1 \\ 0 \\ 1 \end{array} \right] + s \left[ \begin{array}{} 1 \\ 0 \\ 1 \\ 0 \end{array} \right] = \left[ \begin{array}{} 1+s \\ 2+t \\ 3+s \\ 4+t \end{array} \right]$,$s, t$are two parameters. Rewrite:$\left\{ \begin{array}{} x_1 &= 1+5 \\ x_2 &= 2+t \\ x_3 &= 3+s \\ x_4 &= 4+t \end{array} \right. \rightarrow$row-reduced echelon system. Theorem: A homogeneous system with (like one above)$m$linear equations and$n$unknowns, with$n>m$, has at least one non-zero solution. Idea of proof: There will be at most$m1\$'s in the reduced row echelon form. Hence there will be free variables (parameters). Give these parameters non-zero values. Find the dependent variables from the system. That gives us a non-zero solution.