The Matrix Equation, Solution Sets, and Applications
Topics: The matrix equation \(A\mathbf x=\mathbf b\) (§1.4) · Solution sets of linear systems (§1.5) · Applications of linear systems (§1.6). Textbook: Lay, Lay & McDonald, Linear Algebra and Its Applications, 6th ed.
By the end of this week you will be able to:
- compute the product \(A\mathbf x\) in two ways (as a linear combination of columns, and by the row-vector rule), and decide when the product is defined;
- move freely between a linear system, a vector equation, and a matrix equation \(A\mathbf x=\mathbf b\);
- use pivot positions to decide whether \(A\mathbf x=\mathbf b\) is consistent for every \(\mathbf b\), that is, whether the columns of \(A\) span \(\mathbb R^m\);
- write the solution set of a homogeneous or nonhomogeneous system in parametric vector form and describe it geometrically;
- set up and solve linear systems that come from an exchange economy, a chemical reaction, or a network flow.
Day 1: §1.4 The Matrix Equation \(A\mathbf x=\mathbf b\)
Today: we compress a linear combination of vectors into a single product \(A\mathbf x\). This gives a third way to write a linear system, and a clean criterion for when a system is solvable for every right-hand side.
If \(A\) is an \(m\times n\) matrix with columns \(\mathbf a_1,\dots,\mathbf a_n\), and if \(\mathbf x\) is in \(\mathbb R^n\), then the product of \(A\) and \(\mathbf x\), written \(A\mathbf x\), is the linear combination of the columns of \(A\) using the entries of \(\mathbf x\) as weights: \[A\mathbf x=\begin{bmatrix}\mathbf a_1 & \mathbf a_2 & \cdots & \mathbf a_n\end{bmatrix}\begin{bmatrix}x_1\\ \vdots\\ x_n\end{bmatrix}=x_1\mathbf a_1+x_2\mathbf a_2+\cdots+x_n\mathbf a_n.\]
The product is defined only if the number of columns of \(A\) equals the number of entries of \(\mathbf x\). The result \(A\mathbf x\) is a vector in \(\mathbb R^m\) (one entry per row of \(A\)).
Compute \(\begin{bmatrix}1&2&-1\\0&-5&3\end{bmatrix}\begin{bmatrix}4\\3\\7\end{bmatrix}\).
Solution. The matrix is \(2\times 3\) and \(\mathbf x\) has 3 entries, so the product is defined and the answer will be in \(\mathbb R^2\). By the definition, the entries \(4,3,7\) are weights on the three columns: \[\begin{bmatrix}1&2&-1\\0&-5&3\end{bmatrix}\begin{bmatrix}4\\3\\7\end{bmatrix} =4\begin{bmatrix}1\\0\end{bmatrix}+3\begin{bmatrix}2\\-5\end{bmatrix}+7\begin{bmatrix}-1\\3\end{bmatrix} =\begin{bmatrix}4\\0\end{bmatrix}+\begin{bmatrix}6\\-15\end{bmatrix}+\begin{bmatrix}-7\\21\end{bmatrix} =\begin{bmatrix}3\\6\end{bmatrix}.\] Each step is entrywise arithmetic: first scale each column by its weight, then add the three results.
The same definition shows why \(\begin{bmatrix}-4&2\\1&6\\0&1\end{bmatrix}\begin{bmatrix}3\\1\\7\end{bmatrix}\) is not defined: the matrix has 2 columns but the vector has 3 entries, so there is no way to match weights with columns.
Three languages for one problem
Last week we wrote a linear system as a vector equation. The definition of \(A\mathbf x\) lets us go one step further and write it as a single equation between two vectors.
Write the system \[\begin{aligned}x_1+2x_2-x_3&=4\\ -5x_2+3x_3&=1\end{aligned}\] first as a vector equation and then as a matrix equation.
Solution. Step 1 (vector equation). Read the system column by column: the coefficients of \(x_1\) form the vector \(\begin{bmatrix}1\\0\end{bmatrix}\), those of \(x_2\) form \(\begin{bmatrix}2\\-5\end{bmatrix}\), those of \(x_3\) form \(\begin{bmatrix}-1\\3\end{bmatrix}\), and the right-hand side is \(\begin{bmatrix}4\\1\end{bmatrix}\). So the system says \[x_1\begin{bmatrix}1\\0\end{bmatrix}+x_2\begin{bmatrix}2\\-5\end{bmatrix}+x_3\begin{bmatrix}-1\\3\end{bmatrix}=\begin{bmatrix}4\\1\end{bmatrix}.\] (Check the second entries: \(0x_1-5x_2+3x_3=1\) is the second equation.)
Step 2 (matrix equation). The left side is a linear combination of three vectors with weights \(x_1,x_2,x_3\). By the definition of \(A\mathbf x\), that is exactly a matrix times a vector: put the three vectors into the columns of \(A\) and the weights into \(\mathbf x\): \[\begin{bmatrix}1&2&-1\\0&-5&3\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}4\\1\end{bmatrix}.\] Notice that \(A\) is just the coefficient matrix of the original system. Nothing was lost; we only changed the notation.
Let \(A\) be an \(m\times n\) matrix with columns \(\mathbf a_1,\dots,\mathbf a_n\), and let \(\mathbf b\) be in \(\mathbb R^m\). Then the following three objects have exactly the same solution set:
- the matrix equation \(A\mathbf x=\mathbf b\);
- the vector equation \(x_1\mathbf a_1+x_2\mathbf a_2+\cdots+x_n\mathbf a_n=\mathbf b\);
- the linear system whose augmented matrix is \([\,\mathbf a_1\ \ \mathbf a_2\ \cdots\ \mathbf a_n \mid \mathbf b\,]\).
All three are solved in the same way: row reduce the augmented matrix \([A\mid\mathbf b]\).
Why is this useful? Because you may choose whichever form is most natural for a given problem, and switch when convenient. The matrix form is the shortest to write and, as we will see next, the easiest to reason about.
Existence of solutions
The definition of \(A\mathbf x\) says that \(A\mathbf x\) is always a linear combination of the columns of \(A\). Read backwards, this gives:
The equation \(A\mathbf x=\mathbf b\) has a solution if and only if \(\mathbf b\) is a linear combination of the columns of \(A\), that is, if and only if \(\mathbf b\) is in \(\operatorname{Span}\{\mathbf a_1,\dots,\mathbf a_n\}\).
Last week we asked "is this particular \(\mathbf b\) in the span of the columns?" A harder question is: is \(A\mathbf x=\mathbf b\) consistent for every possible \(\mathbf b\)? The next example shows how to attack it.
Let \(A=\begin{bmatrix}1&3&4\\-4&2&-6\\-3&-2&-7\end{bmatrix}\) and \(\mathbf b=\begin{bmatrix}b_1\\b_2\\b_3\end{bmatrix}\). Is \(A\mathbf x=\mathbf b\) consistent for all possible values of \(b_1,b_2,b_3\)?
Solution. We keep \(b_1,b_2,b_3\) as symbols and row reduce the augmented matrix. The operations are the usual ones; the symbols just ride along in the last column.
Step 1. Clear column 1 below the pivot: \(R_2\to R_2+4R_1\) and \(R_3\to R_3+3R_1\): \[\left[\begin{array}{ccc|c}1&3&4&b_1\\-4&2&-6&b_2\\-3&-2&-7&b_3\end{array}\right]\sim \left[\begin{array}{ccc|c}1&3&4&b_1\\0&14&10&b_2+4b_1\\0&7&5&b_3+3b_1\end{array}\right]\]
Step 2. Row 3 is half of row 2 in the coefficient part, so \(R_3\to R_3-\tfrac12R_2\) clears it: \[\sim\left[\begin{array}{ccc|c}1&3&4&b_1\\0&14&10&b_2+4b_1\\0&0&0&b_3+3b_1-\tfrac12(b_2+4b_1)\end{array}\right]\] The last entry simplifies to \(b_1-\tfrac12 b_2+b_3\).
Step 3 (read the last row). It says \(0=b_1-\tfrac12b_2+b_3\). If we choose \(\mathbf b\) so that this number is not zero, for instance \(\mathbf b=(1,0,0)\), the system is inconsistent. So the answer is no: \(A\mathbf x=\mathbf b\) is not consistent for every \(\mathbf b\).
Bonus. The same computation describes exactly which \(\mathbf b\) work: those with \(b_1-\tfrac12b_2+b_3=0\). This is the equation of a plane through the origin in \(\mathbb R^3\). That plane is \(\operatorname{Span}\{\mathbf a_1,\mathbf a_2,\mathbf a_3\}\): the three columns of \(A\) only span a plane, not all of \(\mathbb R^3\).
Look at why Example 3 failed: the echelon form of \(A\) has a row of zeros, so \(A\) has only 2 pivot positions for its 3 rows. If \(A\) had a pivot in every row, no row of the augmented matrix could ever become \([\,0\ 0\ 0 \mid c\,]\) with \(c\ne0\), whatever \(\mathbf b\) is. This is the idea behind the next theorem.
A set of vectors \(\{\mathbf v_1,\dots,\mathbf v_p\}\) in \(\mathbb R^m\) spans (or generates) \(\mathbb R^m\) if every vector in \(\mathbb R^m\) is a linear combination of \(\mathbf v_1,\dots,\mathbf v_p\), that is, if \(\operatorname{Span}\{\mathbf v_1,\dots,\mathbf v_p\}=\mathbb R^m\). "The columns of \(A\) span \(\mathbb R^m\)" means every \(\mathbf b\) in \(\mathbb R^m\) is a linear combination of the columns of \(A\).
For example, the columns of \(\begin{bmatrix}1&0\\0&1\end{bmatrix}\) span \(\mathbb R^2\), because \(\begin{bmatrix}b_1\\b_2\end{bmatrix}=b_1\begin{bmatrix}1\\0\end{bmatrix}+b_2\begin{bmatrix}0\\1\end{bmatrix}\) for every \(b_1,b_2\). The columns of the matrix in Example 3 do not span \(\mathbb R^3\).
Let \(A\) be an \(m\times n\) matrix. The following statements are logically equivalent: for a given \(A\), either all four are true or all four are false.
- For each \(\mathbf b\) in \(\mathbb R^m\), the equation \(A\mathbf x=\mathbf b\) has a solution.
- Each \(\mathbf b\) in \(\mathbb R^m\) is a linear combination of the columns of \(A\).
- The columns of \(A\) span \(\mathbb R^m\).
- \(A\) has a pivot position in every row.
Statements (a), (b), (c) are three wordings of one idea (the key fact above plus the definition of span). Statement (d) is the one you can compute: row reduce \(A\) and count the pivot rows. The reasoning for (a) \(\Leftrightarrow\) (d) is the one given after Example 3; we do not go through the formal proof here.
Theorem 4 is about the coefficient matrix \(A\). If the augmented matrix \([A\mid\mathbf b]\) has a pivot in every row, that tells you nothing: the last pivot might sit in the augmented column, which means the system is inconsistent. Always apply (d) to \(A\) alone.
A faster way to compute \(A\mathbf x\)
The definition builds \(A\mathbf x\) column by column. When computing by hand it is usually faster to go row by row. To see why, compute a product with symbolic entries: \[\begin{bmatrix}2&3&4\\-1&5&-3\\6&-2&8\end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix} =x_1\begin{bmatrix}2\\-1\\6\end{bmatrix}+x_2\begin{bmatrix}3\\5\\-2\end{bmatrix}+x_3\begin{bmatrix}4\\-3\\8\end{bmatrix} =\begin{bmatrix}2x_1+3x_2+4x_3\\-x_1+5x_2-3x_3\\6x_1-2x_2+8x_3\end{bmatrix}.\] The first entry of the result, \(2x_1+3x_2+4x_3\), uses only the first row of \(A\) and the entries of \(\mathbf x\): multiply matching entries and add. The same holds for each row.
If the product \(A\mathbf x\) is defined, then the \(i\)-th entry of \(A\mathbf x\) is the sum of the products of corresponding entries from row \(i\) of \(A\) and from the vector \(\mathbf x\).
(a) Compute \(\begin{bmatrix}2&-3\\8&0\\-5&2\end{bmatrix}\begin{bmatrix}4\\7\end{bmatrix}\) using the row-vector rule.
(b) Compute \(\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}r\\s\\t\end{bmatrix}\).
Solution.
(a) The matrix is \(3\times 2\) and the vector has 2 entries, so the product is defined and lives in \(\mathbb R^3\). Take one row at a time and pair it with \(\begin{bmatrix}4\\7\end{bmatrix}\): \[\begin{bmatrix}2\cdot4+(-3)\cdot7\\ 8\cdot4+0\cdot7\\ (-5)\cdot4+2\cdot7\end{bmatrix}=\begin{bmatrix}8-21\\32+0\\-20+14\end{bmatrix}=\begin{bmatrix}-13\\32\\-6\end{bmatrix}.\] You can confirm with the definition: \(4\begin{bmatrix}2\\8\\-5\end{bmatrix}+7\begin{bmatrix}-3\\0\\2\end{bmatrix}=\begin{bmatrix}8-21\\32\\-20+14\end{bmatrix}\), the same numbers arranged differently.
(b) Row 1 is \((1,0,0)\), so the first entry is \(1\cdot r+0\cdot s+0\cdot t=r\). Likewise the second entry is \(s\) and the third is \(t\): \[\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}r\\s\\t\end{bmatrix}=\begin{bmatrix}r\\s\\t\end{bmatrix}.\] The matrix in (b), with 1's on the diagonal and 0's elsewhere, is the identity matrix \(I\) (or \(I_3\) to record its size). The computation shows \(I\mathbf x=\mathbf x\) for every \(\mathbf x\) in \(\mathbb R^3\). The same holds for the \(n\times n\) identity matrix \(I_n\) and every \(\mathbf x\) in \(\mathbb R^n\).
Algebraic properties of \(A\mathbf x\)
If \(A\) is an \(m\times n\) matrix, \(\mathbf u\) and \(\mathbf v\) are vectors in \(\mathbb R^n\), and \(c\) is a scalar, then
- \(A(\mathbf u+\mathbf v)=A\mathbf u+A\mathbf v\);
- \(A(c\mathbf u)=c(A\mathbf u)\).
Both facts follow from the definition of \(A\mathbf x\) and the ordinary rules of vector arithmetic (the weights \(u_i+v_i\) split into \(u_i\) and \(v_i\), and the weights \(cu_i\) pull out a common factor \(c\)). We will use this theorem again and again; the full proof is in the textbook.
Let \(A=\begin{bmatrix}2&5\\3&1\end{bmatrix}\), \(\mathbf u=\begin{bmatrix}4\\-1\end{bmatrix}\), \(\mathbf v=\begin{bmatrix}-3\\5\end{bmatrix}\). Verify that \(A(\mathbf u+\mathbf v)=A\mathbf u+A\mathbf v\).
Solution. Left side. First add: \(\mathbf u+\mathbf v=\begin{bmatrix}4-3\\-1+5\end{bmatrix}=\begin{bmatrix}1\\4\end{bmatrix}\). Then multiply by the row-vector rule: \[A(\mathbf u+\mathbf v)=\begin{bmatrix}2\cdot1+5\cdot4\\3\cdot1+1\cdot4\end{bmatrix}=\begin{bmatrix}22\\7\end{bmatrix}.\] Right side. Multiply first, add second: \[A\mathbf u=\begin{bmatrix}8-5\\12-1\end{bmatrix}=\begin{bmatrix}3\\11\end{bmatrix},\qquad A\mathbf v=\begin{bmatrix}-6+25\\-9+5\end{bmatrix}=\begin{bmatrix}19\\-4\end{bmatrix},\qquad A\mathbf u+A\mathbf v=\begin{bmatrix}22\\7\end{bmatrix}.\] Both sides give \(\begin{bmatrix}22\\7\end{bmatrix}\), as Theorem 5 promises. The point of the theorem is that this always happens, so you never need to check it again.
Day 2: §1.5 Solution Sets of Linear Systems
Today: we describe the whole solution set of a system with vectors. Homogeneous systems come first; then we see that every consistent system has a solution set that is a shifted copy of a homogeneous one.
Homogeneous systems
A system of linear equations is homogeneous if it can be written as \(A\mathbf x=\mathbf 0\), where \(A\) is an \(m\times n\) matrix and \(\mathbf 0\) is the zero vector in \(\mathbb R^m\). Such a system always has at least one solution, \(\mathbf x=\mathbf 0\), called the trivial solution. A nontrivial solution is a nonzero vector \(\mathbf x\) with \(A\mathbf x=\mathbf 0\).
For example, \(x_1+2x_2=0\) is homogeneous; \(x_1=0,\ x_2=0\) is its trivial solution and \(x_1=-2,\ x_2=1\) is a nontrivial one. The equation \(x_1+2x_2=3\) is not homogeneous.
Because \(\mathbf 0\) is always a solution, a homogeneous system is never inconsistent. The only interesting question is uniqueness: is \(\mathbf 0\) the only solution, or are there others? The existence-and-uniqueness theorem from last week answers this immediately.
The homogeneous equation \(A\mathbf x=\mathbf 0\) has a nontrivial solution if and only if the equation has at least one free variable.
Determine whether the system \[\begin{aligned}3x_1+5x_2-4x_3&=0\\-3x_1-2x_2+4x_3&=0\\6x_1+x_2-8x_3&=0\end{aligned}\] has a nontrivial solution, and describe its solution set.
Solution. Step 1 (echelon form). Write the augmented matrix and clear column 1: \(R_2\to R_2+R_1\), \(R_3\to R_3-2R_1\). Then clear column 2: \(R_3\to R_3+3R_2\). \[\left[\begin{array}{ccc|c}3&5&-4&0\\-3&-2&4&0\\6&1&-8&0\end{array}\right]\sim \left[\begin{array}{ccc|c}3&5&-4&0\\0&3&0&0\\0&-9&0&0\end{array}\right]\sim \left[\begin{array}{ccc|c}3&5&-4&0\\0&3&0&0\\0&0&0&0\end{array}\right]\] Pivots are in columns 1 and 2, so \(x_3\) is free. By the key fact, nontrivial solutions exist, one for each nonzero choice of \(x_3\).
Step 2 (reduced form). To write the solutions we continue to RREF: \(R_2\to\tfrac13R_2\), then \(R_1\to R_1-5R_2\), then \(R_1\to\tfrac13R_1\): \[\sim\left[\begin{array}{ccc|c}1&0&-\tfrac43&0\\0&1&0&0\\0&0&0&0\end{array}\right] \qquad\text{that is}\qquad \begin{aligned}x_1-\tfrac43x_3&=0\\x_2&=0\\0&=0\end{aligned}\]
Step 3 (solve for the basic variables). \(x_1=\tfrac43x_3\), \(x_2=0\), with \(x_3\) free.
Step 4 (write the solution as a vector and factor out the free variable). \[\mathbf x=\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}=\begin{bmatrix}\tfrac43x_3\\0\\x_3\end{bmatrix}=x_3\begin{bmatrix}\tfrac43\\0\\1\end{bmatrix}=x_3\mathbf v,\qquad \mathbf v=\begin{bmatrix}\tfrac43\\0\\1\end{bmatrix}.\] Every solution is a multiple of \(\mathbf v\), and \(x_3=0\) gives the trivial solution. Geometrically, the solution set is \(\operatorname{Span}\{\mathbf v\}\), a line through the origin in \(\mathbb R^3\).
Check. \(A\mathbf v\) should be \(\mathbf 0\): first row \(3\cdot\tfrac43+0-4=0\), second row \(-4+0+4=0\), third row \(8+0-8=0\). Correct. (If you prefer whole numbers, \(3\mathbf v=(4,0,3)\) spans the same line.)
Describe all solutions of the homogeneous "system" consisting of the single equation \(10x_1-3x_2-2x_3=0\).
Solution. There is only one equation, so no matrix work is needed. The pivot variable is \(x_1\) (first nonzero coefficient); \(x_2\) and \(x_3\) are free. Solve for \(x_1\): \(x_1=0.3x_2+0.2x_3\). Write the solution as a vector and split it according to the free variables: \[\mathbf x=\begin{bmatrix}0.3x_2+0.2x_3\\x_2\\x_3\end{bmatrix} =\begin{bmatrix}0.3x_2\\x_2\\0\end{bmatrix}+\begin{bmatrix}0.2x_3\\0\\x_3\end{bmatrix} =x_2\underbrace{\begin{bmatrix}0.3\\1\\0\end{bmatrix}}_{\mathbf u}+x_3\underbrace{\begin{bmatrix}0.2\\0\\1\end{bmatrix}}_{\mathbf v}\qquad(x_2,x_3\text{ free}).\] Every solution is a linear combination of \(\mathbf u\) and \(\mathbf v\), so the solution set is \(\operatorname{Span}\{\mathbf u,\mathbf v\}\). Neither vector is a multiple of the other (look at the last two entries), so this is a plane through the origin in \(\mathbb R^3\).
Check. \(10(0.3)-3(1)-2(0)=0\) and \(10(0.2)-0-2(1)=0\), so \(\mathbf u\) and \(\mathbf v\) really are solutions; Theorem 5 then guarantees that every combination of them is a solution too.
Examples 1 and 2 show the general pattern: the solution set of \(A\mathbf x=\mathbf 0\) can always be written as \(\operatorname{Span}\{\mathbf v_1,\dots,\mathbf v_p\}\) for suitable vectors. If the only solution is \(\mathbf 0\), the solution set is \(\operatorname{Span}\{\mathbf 0\}=\{\mathbf 0\}\). One free variable gives a line through the origin; two free variables give a plane through the origin.
Equation \(10x_1-3x_2-2x_3=0\) is an implicit description of a plane. The equation \[\mathbf x=s\mathbf u+t\mathbf v\qquad(s,t\text{ in }\mathbb R)\] from Example 2 is an explicit description of the same plane, called a parametric vector equation. Likewise \(\mathbf x=t\mathbf v\) (\(t\) in \(\mathbb R\)) is a parametric vector equation of the line in Example 1. Whenever a solution set is written this way, with vectors and free parameters, we say the solution is in parametric vector form.
Nonhomogeneous systems
Now replace \(\mathbf 0\) by a nonzero \(\mathbf b\). The procedure is the same; the answer picks up one extra vector.
Describe all solutions of \(A\mathbf x=\mathbf b\), where \(A=\begin{bmatrix}3&5&-4\\-3&-2&4\\6&1&-8\end{bmatrix}\) (the matrix of Example 1) and \(\mathbf b=\begin{bmatrix}7\\-1\\-4\end{bmatrix}\).
Solution. Step 1. Apply exactly the operations of Example 1 to \([A\mid\mathbf b]\): \(R_2+R_1\), \(R_3-2R_1\), \(R_3+3R_2\), then \(\tfrac13R_2\), \(R_1-5R_2\), \(\tfrac13R_1\): \[\left[\begin{array}{ccc|c}3&5&-4&7\\-3&-2&4&-1\\6&1&-8&-4\end{array}\right]\sim \left[\begin{array}{ccc|c}3&5&-4&7\\0&3&0&6\\0&-9&0&-18\end{array}\right]\sim \left[\begin{array}{ccc|c}1&0&-\tfrac43&-1\\0&1&0&2\\0&0&0&0\end{array}\right]\] The last row is \(0=0\), so the system is consistent.
Step 2. Read off the basic variables: \(x_1=-1+\tfrac43x_3\), \(x_2=2\), with \(x_3\) free.
Step 3. Write the general solution as a vector and separate the constant part from the part that depends on \(x_3\): \[\mathbf x=\begin{bmatrix}-1+\tfrac43x_3\\2\\x_3\end{bmatrix} =\begin{bmatrix}-1\\2\\0\end{bmatrix}+x_3\begin{bmatrix}\tfrac43\\0\\1\end{bmatrix} =\mathbf p+x_3\mathbf v.\] With a general parameter \(t\): \(\mathbf x=\mathbf p+t\mathbf v\) (\(t\) in \(\mathbb R\)).
Interpretation. The vector \(\mathbf v\) is the same vector that described the solutions of \(A\mathbf x=\mathbf 0\) in Example 1. The new vector \(\mathbf p=(-1,2,0)\) is one particular solution of \(A\mathbf x=\mathbf b\) (it is \(t=0\)). So the solutions of \(A\mathbf x=\mathbf b\) are obtained by adding \(\mathbf p\) to every solution of \(A\mathbf x=\mathbf 0\).
Check. \(A\mathbf p\): first row \(-3+10+0=7\), second \(3-4+0=-1\), third \(-6+2+0=-4\). This is \(\mathbf b\). And \(A\mathbf v=\mathbf 0\) was checked in Example 1.
Figure 1 shows the geometry. Adding a fixed vector \(\mathbf p\) to every point of a line \(L\) through the origin slides the whole line, without turning it, to a parallel line through \(\mathbf p\). We say the line is translated by \(\mathbf p\). In Example 3 the solution set of \(A\mathbf x=\mathbf b\) is the line through \(\mathbf p\) parallel to the solution set of \(A\mathbf x=\mathbf 0\). This is a general fact.
Suppose the equation \(A\mathbf x=\mathbf b\) is consistent for some given \(\mathbf b\), and let \(\mathbf p\) be a solution. Then the solution set of \(A\mathbf x=\mathbf b\) is the set of all vectors of the form \[\mathbf w=\mathbf p+\mathbf v_h,\] where \(\mathbf v_h\) is any solution of the homogeneous equation \(A\mathbf x=\mathbf 0\).
Why \(\mathbf p+\mathbf v_h\) is a solution: by Theorem 5, \(A(\mathbf p+\mathbf v_h)=A\mathbf p+A\mathbf v_h=\mathbf b+\mathbf 0=\mathbf b\). The other direction (every solution has this form) is Exercise 37 in the textbook.
In words: if \(A\mathbf x=\mathbf b\) has a solution, its solution set is the solution set of \(A\mathbf x=\mathbf 0\) translated by any one particular solution \(\mathbf p\). Even when \(n>3\), keep this picture in mind: the solution set of a consistent system with \(\mathbf b\ne\mathbf 0\) is a single point, or a line, or a plane (or a higher-dimensional flat set) that does not pass through the origin.
Theorem 6 and Figure 1 apply only when \(A\mathbf x=\mathbf b\) has at least one solution \(\mathbf p\). If \(A\mathbf x=\mathbf b\) is inconsistent, its solution set is empty, and there is nothing to translate.
- Row reduce the augmented matrix to reduced echelon form.
- Express each basic variable in terms of the free variables (if any).
- Write a typical solution \(\mathbf x\) as a vector whose entries depend on the free variables.
- Decompose \(\mathbf x\) into a linear combination of vectors with numeric entries, using the free variables as parameters.
Checking your answer. Multiply \(A\) by each vector you found. The constant vector \(\mathbf p\) must give \(\mathbf b\); each vector multiplied by a free variable must give \(\mathbf 0\). If a product comes out wrong, the mistake is in the row reduction or the decomposition.
(a) Find a parametric equation of the line through \(\mathbf a=\begin{bmatrix}-2\\0\end{bmatrix}\) parallel to \(\mathbf b=\begin{bmatrix}-5\\3\end{bmatrix}\).
(b) Find a parametric equation of the line \(M\) through \(\mathbf p=\begin{bmatrix}2\\-5\end{bmatrix}\) and \(\mathbf q=\begin{bmatrix}-3\\1\end{bmatrix}\).
Solution.
(a) A line through a point \(\mathbf a\) in the direction of \(\mathbf b\) is the translate of \(\operatorname{Span}\{\mathbf b\}\) by \(\mathbf a\): \(\mathbf x=\mathbf a+t\mathbf b\), that is, \[\mathbf x=\begin{bmatrix}-2\\0\end{bmatrix}+t\begin{bmatrix}-5\\3\end{bmatrix}\qquad(t\text{ in }\mathbb R).\] When \(t=0\) we are at \(\mathbf a\); each unit increase of \(t\) moves us by \(\mathbf b\).
(b) We need a point on \(M\) and a direction. The point can be \(\mathbf p\). For the direction, the arrow from \(\mathbf p\) to \(\mathbf q\) lies along \(M\), and that arrow is \(\mathbf q-\mathbf p=\begin{bmatrix}-3-2\\1-(-5)\end{bmatrix}=\begin{bmatrix}-5\\6\end{bmatrix}\). Therefore \[\mathbf x=\mathbf p+t(\mathbf q-\mathbf p)=\begin{bmatrix}2\\-5\end{bmatrix}+t\begin{bmatrix}-5\\6\end{bmatrix}\qquad(t\text{ in }\mathbb R).\] Check. \(t=0\) gives \(\mathbf p\), and \(t=1\) gives \(\begin{bmatrix}2-5\\-5+6\end{bmatrix}=\mathbf q\), so both given points are on the line.
Each of the equations \(x_1+4x_2-5x_3=0\) and \(2x_1-x_2+8x_3=9\) describes a plane in \(\mathbb R^3\). Do the planes intersect? If so, describe the intersection.
Solution. A point lies on both planes exactly when it solves the system of the two equations, so we solve the system. \(R_2\to R_2-2R_1\), then \(R_2\to-\tfrac19R_2\), then \(R_1\to R_1-4R_2\): \[\left[\begin{array}{ccc|c}1&4&-5&0\\2&-1&8&9\end{array}\right]\sim \left[\begin{array}{ccc|c}1&4&-5&0\\0&-9&18&9\end{array}\right]\sim \left[\begin{array}{ccc|c}1&0&3&4\\0&1&-2&-1\end{array}\right]\] The system is consistent (no impossible row), so the planes do intersect. The variables \(x_1,x_2\) are basic and \(x_3\) is free: \(x_1=4-3x_3\), \(x_2=-1+2x_3\). In parametric vector form, \[\mathbf x=\begin{bmatrix}4-3x_3\\-1+2x_3\\x_3\end{bmatrix}=\begin{bmatrix}4\\-1\\0\end{bmatrix}+x_3\begin{bmatrix}-3\\2\\1\end{bmatrix}=\mathbf p+x_3\mathbf v.\] One free variable means the intersection is a line: the line through \(\mathbf p=(4,-1,0)\) in the direction \(\mathbf v=(-3,2,1)\).
Check. \(\mathbf p\) in both planes: \(4-4-0=0\) and \(8+1+0=9\). \(\mathbf v\) in both homogeneous versions: \(-3+8-5=0\) and \(-6-2+8=0\).
Day 3 (applications day): §1.6 Applications of Linear Systems
Today: three real situations that lead to linear systems with many solutions: an exchange economy, a chemical reaction, and a traffic network. The mathematics is this week's; the work is in setting up the equations correctly.
1. An exchange economy (Leontief)
Divide a nation's economy into sectors. Suppose that for each sector we know how its total yearly output is split among all the sectors, including itself. Call the total dollar value of a sector's output the price of that output. Leontief proved the following.
There exist equilibrium prices that can be assigned to the total outputs of the sectors in such a way that the income of each sector exactly balances its expenses.
We will not prove this; we will compute the prices. The data is recorded in an exchange table: each column lists the fractions of one sector's output that go to the various sectors, so each column sums to 1.
An economy has three sectors, Coal, Electric, and Steel. The output of each sector is distributed as in Table 1 (entries in a column are fractions of that sector's total output).
| Distribution of output from | Purchased by | ||
|---|---|---|---|
| Coal | Electric | Steel | |
| 0.0 | 0.4 | 0.6 | Coal |
| 0.6 | 0.1 | 0.2 | Electric |
| 0.4 | 0.5 | 0.2 | Steel |
Let \(p_C,p_E,p_S\) be the prices of the total annual outputs of Coal, Electric, and Steel. Find equilibrium prices that make each sector's income equal to its expenses.
Solution. How to read the table. A sector looks down a column to see where its output goes, and across a row to see what it buys. The second column says Electric sends 40% of its output to Coal, 10% to itself, and 50% to Steel. The first row says Coal receives 40% of Electric's output and 60% of Steel's output.
Step 1 (one equation per row). Coal's expenses are what it pays for these shares: \(0.4p_E+0.6p_S\). Its income is \(p_C\). Balance gives \[p_C=0.4p_E+0.6p_S.\] The second row (Electric buys 60% of Coal, 10% of Electric, 20% of Steel) gives \(p_E=0.6p_C+0.1p_E+0.2p_S\), and the third row gives \(p_S=0.4p_C+0.5p_E+0.2p_S\).
Step 2 (a homogeneous system). Move every term to the left and combine like terms (for instance \(p_E-0.1p_E=0.9p_E\)): \[\begin{aligned}p_C-0.4p_E-0.6p_S&=0\\-0.6p_C+0.9p_E-0.2p_S&=0\\-0.4p_C-0.5p_E+0.8p_S&=0\end{aligned}\] This is homogeneous, so the zero prices are always a solution; we want a nontrivial one.
Step 3 (row reduce). \(R_2\to R_2+0.6R_1\), \(R_3\to R_3+0.4R_1\): \[\left[\begin{array}{ccc|c}1&-0.4&-0.6&0\\-0.6&0.9&-0.2&0\\-0.4&-0.5&0.8&0\end{array}\right]\sim \left[\begin{array}{ccc|c}1&-0.4&-0.6&0\\0&0.66&-0.56&0\\0&-0.66&0.56&0\end{array}\right]\] Rows 2 and 3 are negatives of each other, so \(R_3\to R_3+R_2\) gives a zero row. This is not an accident: the columns of the table sum to 1, which forces the three equations to be dependent, and that is exactly why a nontrivial solution exists. Now scale \(R_2\) by \(1/0.66\) (rounded to two decimals, \(0.56/0.66\approx0.85\)) and clear above: \(R_1\to R_1+0.4R_2\): \[\sim\left[\begin{array}{ccc|c}1&-0.4&-0.6&0\\0&1&-0.85&0\\0&0&0&0\end{array}\right]\sim \left[\begin{array}{ccc|c}1&0&-0.94&0\\0&1&-0.85&0\\0&0&0&0\end{array}\right]\]
Step 4 (read the solution). \(p_C=0.94p_S\), \(p_E=0.85p_S\), with \(p_S\) free: \[\mathbf p=\begin{bmatrix}p_C\\p_E\\p_S\end{bmatrix}=p_S\begin{bmatrix}0.94\\0.85\\1\end{bmatrix}.\] Any nonnegative choice of \(p_S\) gives equilibrium prices. Taking \(p_S=100\) (say, 100 million dollars) gives \(p_C=94\) and \(p_E=85\). Incomes and expenses match if Coal's output is priced at 94, Electric's at 85, and Steel's at 100.
Check on the first row (before rounding). Coal's expenses: \(0.4(85)+0.6(100)=34+60=94=p_C\). Good.
2. Balancing chemical equations
When propane burns, propane \(\mathrm{C_3H_8}\) combines with oxygen \(\mathrm{O_2}\) to form carbon dioxide \(\mathrm{CO_2}\) and water \(\mathrm{H_2O}\): \[(x_1)\,\mathrm{C_3H_8}+(x_2)\,\mathrm{O_2}\ \longrightarrow\ (x_3)\,\mathrm{CO_2}+(x_4)\,\mathrm{H_2O}.\] To balance the equation we need whole numbers \(x_1,\dots,x_4\) such that the number of atoms of each element (C, H, O) on the left equals the number on the right; atoms are neither created nor destroyed.
The method: for each molecule build a vector in \(\mathbb R^3\) listing its atoms per molecule, in the order (carbon, hydrogen, oxygen): \[\mathrm{C_3H_8}:\begin{bmatrix}3\\8\\0\end{bmatrix},\quad \mathrm{O_2}:\begin{bmatrix}0\\0\\2\end{bmatrix},\quad \mathrm{CO_2}:\begin{bmatrix}1\\0\\2\end{bmatrix},\quad \mathrm{H_2O}:\begin{bmatrix}0\\2\\1\end{bmatrix}.\]
Find the smallest whole numbers \(x_1,x_2,x_3,x_4\) that balance the reaction above.
Solution. Step 1 (vector equation). "Atoms on the left = atoms on the right" is, entry by entry, \[x_1\begin{bmatrix}3\\8\\0\end{bmatrix}+x_2\begin{bmatrix}0\\0\\2\end{bmatrix}=x_3\begin{bmatrix}1\\0\\2\end{bmatrix}+x_4\begin{bmatrix}0\\2\\1\end{bmatrix}.\] Move everything to the left (this changes the signs of the last two vectors) to get a homogeneous vector equation: \[x_1\begin{bmatrix}3\\8\\0\end{bmatrix}+x_2\begin{bmatrix}0\\0\\2\end{bmatrix}+x_3\begin{bmatrix}-1\\0\\-2\end{bmatrix}+x_4\begin{bmatrix}0\\-2\\-1\end{bmatrix}=\begin{bmatrix}0\\0\\0\end{bmatrix}.\]
Step 2 (row reduce). The augmented matrix and its reduction. First swap \(R_2\leftrightarrow R_3\) so that column 2 has a pivot in row 2; then \(R_3\to R_3-\tfrac83R_1\): \[\left[\begin{array}{cccc|c}3&0&-1&0&0\\8&0&0&-2&0\\0&2&-2&-1&0\end{array}\right]\sim \left[\begin{array}{cccc|c}3&0&-1&0&0\\0&2&-2&-1&0\\0&0&\tfrac83&-2&0\end{array}\right]\] Scale the rows (\(\tfrac13R_1\), \(\tfrac12R_2\), \(\tfrac38R_3\)), then clear above the third pivot (\(R_1\to R_1+\tfrac13R_3\), \(R_2\to R_2+R_3\)): \[\sim\left[\begin{array}{cccc|c}1&0&-\tfrac13&0&0\\0&1&-1&-\tfrac12&0\\0&0&1&-\tfrac34&0\end{array}\right]\sim \left[\begin{array}{cccc|c}1&0&0&-\tfrac14&0\\0&1&0&-\tfrac54&0\\0&0&1&-\tfrac34&0\end{array}\right]\]
Step 3 (general solution). \(x_4\) is free and \[x_1=\tfrac14x_4,\qquad x_2=\tfrac54x_4,\qquad x_3=\tfrac34x_4.\]
Step 4 (choose integers). Chemical coefficients must be whole numbers. The smallest choice of \(x_4\) that clears the denominators is \(x_4=4\), which gives \(x_1=1\), \(x_2=5\), \(x_3=3\). The balanced equation is \[\mathrm{C_3H_8}+5\,\mathrm{O_2}\ \longrightarrow\ 3\,\mathrm{CO_2}+4\,\mathrm{H_2O}.\] Check. Carbon: \(3=3\). Hydrogen: \(8=8\). Oxygen: \(10=6+4\). Doubling every coefficient would also balance the equation (it is another point on the same line of solutions), but chemists prefer the smallest whole numbers.
3. Network flow
Linear systems appear whenever a quantity flows through a network: traffic in city streets, current in a circuit, goods from producers to consumers. A network consists of points called junctions (or nodes) joined by branches. Each branch has a direction of flow and a flow amount, either known or written as a variable.
The total flow into a junction equals the total flow out of that junction, and the total flow into the whole network equals the total flow out of it. Flow is conserved.
Figure 2 shows the simplest case. Each junction gives one linear equation; the problem is to find the flow in every branch when only partial information (for instance the flows entering and leaving the network) is known.
The network in Figure 3 shows the traffic flow (vehicles per hour) on several one-way streets. Determine the general flow pattern.
Solution. Step 1 (label and write one equation per junction). At each intersection, flow in equals flow out:
| Intersection | Flow in | Flow out | |
|---|---|---|---|
| A | \(300+500\) | \(=\) | \(x_1+x_2\) |
| B | \(x_2+x_4\) | \(=\) | \(300+x_3\) |
| C | \(100+400\) | \(=\) | \(x_4+x_5\) |
| D | \(x_1+x_5\) | \(=\) | \(600\) |
Also, the total flow into the network, \(500+300+100+400=1300\), equals the total flow out, \(300+x_3+600\). This simplifies to \(x_3=400\).
Step 2 (the system). Rearranging, with unknowns on the left: \[\begin{aligned}x_1+x_2&=800\\x_2-x_3+x_4&=300\\x_4+x_5&=500\\x_1+x_5&=600\\x_3&=400\end{aligned}\]
Step 3 (row reduce). Row reduction of the augmented matrix (five rows, five columns plus the augmented column) leads to \[\begin{aligned}x_1+x_5&=600\\x_2-x_5&=200\\x_3&=400\\x_4+x_5&=500\end{aligned}\] You can confirm this quickly without matrices: from \(x_3=400\) the second equation becomes \(x_2+x_4=700\); the third gives \(x_4=500-x_5\), hence \(x_2=200+x_5\); the fourth gives \(x_1=600-x_5\); and then the first equation, \(x_1+x_2=800\), is automatically satisfied, which is the row that becomes zero.
Step 4 (general flow pattern). \(x_5\) is free: \[x_1=600-x_5,\qquad x_2=200+x_5,\qquad x_3=400,\qquad x_4=500-x_5,\qquad x_5\text{ free}.\]
Step 5 (physical constraints). A negative flow would mean traffic against the arrow, which is impossible on one-way streets. So every variable must be \(\ge 0\). From \(x_4=500-x_5\ge0\) we get \(x_5\le500\); with \(x_5\ge0\) this gives \(0\le x_5\le500\). Then \(x_1=600-x_5\) ranges over \(100\le x_1\le600\) and \(x_2=200+x_5\) over \(200\le x_2\le700\). Measuring a single flow, \(x_5\), would determine the whole pattern.
Homework 2: Sections 1.4–1.6 (100 points)
- Write your name and surname in the field above.
- Show your work: for computational questions, the row operations or the reasoning must be visible, not just the final answer. In the row-reduction boxes, write one operation per step (for example
R2 -> R2 + 3R1) and the matrix you obtain after it. Entries may be numbers, fractions like-4/3, or symbols likeb2+3b1. - When finished, click "Save homework as PDF" at the bottom, save the PDF, and upload it to Canvas.
- Your answers are saved automatically in this browser only. If you open this file on a different computer or browser, your answers will not appear there.
- Estimated workload: 2–3 hours.
Question 1
(a) [3 pts] Compute \(\begin{bmatrix}6&5\\-4&-3\\7&6\end{bmatrix}\begin{bmatrix}1\\-3\end{bmatrix}\) in two ways: first using the definition (as a linear combination of the columns), then using the row-vector rule. Show both computations.
(b) [3 pts] Is the product \(\begin{bmatrix}-4&2\\1&6\\0&1\end{bmatrix}\begin{bmatrix}3\\1\\7\end{bmatrix}\) defined? If it is, compute it; if not, explain why.
(c) [4 pts] It is given that \(\begin{bmatrix}3&-4&2\\6&-3&4\\-8&9&-5\end{bmatrix}\begin{bmatrix}-4\\-1\\3\end{bmatrix}=\begin{bmatrix}-2\\-9\\8\end{bmatrix}\). Use this fact, and no row operations, to find scalars \(c_1,c_2,c_3\) such that \[\begin{bmatrix}-2\\-9\\8\end{bmatrix}=c_1\begin{bmatrix}3\\6\\-8\end{bmatrix}+c_2\begin{bmatrix}-4\\-3\\9\end{bmatrix}+c_3\begin{bmatrix}2\\4\\-5\end{bmatrix}.\]
Question 2
Let \(A=\begin{bmatrix}1&2&4\\0&1&5\\-2&-4&-3\end{bmatrix}\) and \(\mathbf b=\begin{bmatrix}-2\\2\\9\end{bmatrix}\).
(a) [10 pts] Write the augmented matrix of the linear system that corresponds to \(A\mathbf x=\mathbf b\) in the first grid below, then row reduce it step by step (add one box per row operation).
(b) [5 pts] Solve the system and write the solution as a vector \(\mathbf x\). State whether the solution is unique, and verify your answer by computing \(A\mathbf x\) with the row-vector rule.
Question 3
(a) [15 pts] Let \(A=\begin{bmatrix}1&-3&-4\\-3&2&6\\5&-1&-8\end{bmatrix}\) and \(\mathbf b=\begin{bmatrix}b_1\\b_2\\b_3\end{bmatrix}\). Show that the equation \(A\mathbf x=\mathbf b\) does not have a solution for all possible \(\mathbf b\), and describe the set of all \(\mathbf b\) for which \(A\mathbf x=\mathbf b\) does have a solution. Row reduce the augmented matrix with the symbols \(b_1,b_2,b_3\) in the last column (write expressions such as b2+3b1 in the cells). After the reduction, a final answer of the form "the system has a solution if and only if ... = 0", with an equation in \(b_1,b_2,b_3\), is sufficient.
Conclusion for (a): the condition on \(b_1,b_2,b_3\).
(b) [5 pts] Could a set of three vectors in \(\mathbb R^4\) span all of \(\mathbb R^4\)? Explain. What about \(n\) vectors in \(\mathbb R^m\) when \(n\) is less than \(m\)?
Question 4
(a) [15 pts] Describe all solutions of the system \[\begin{aligned}x_1+3x_2-5x_3&=4\\x_1+4x_2-8x_3&=7\\-3x_1-7x_2+9x_3&=-6\end{aligned}\] in parametric vector form \(\mathbf x=\mathbf p+t\mathbf v\). Row reduce the augmented matrix below and write the result in the text box.
(b) [10 pts] Now consider the corresponding homogeneous system \(A\mathbf x=\mathbf 0\), with the same coefficient matrix. Write its solution set in parametric vector form, and state which vector in your answer to (a) is a particular solution of \(A\mathbf x=\mathbf b\) and which vector is a solution of the homogeneous system (Theorem 6).
Question 5
(a) [10 pts] Suppose \(A\) is row equivalent to \(\begin{bmatrix}1&-2&-9&5\\0&1&2&-6\end{bmatrix}\). Describe all solutions of \(A\mathbf x=\mathbf 0\) in parametric vector form.
(b) [5 pts] Let \(A=\begin{bmatrix}-2&-6\\7&21\\-3&-9\end{bmatrix}\). Find one nontrivial solution of \(A\mathbf x=\mathbf 0\) by inspection, without row operations. (Think of \(A\mathbf x=\mathbf 0\) as a vector equation and look at how the two columns are related.) Verify your solution.
Question 6
Consider an economy with three sectors: Chemicals & Metals, Fuels & Power, and Machinery. Chemicals sells 30% of its output to Fuels and 50% to Machinery, and retains the rest. Fuels sells 80% of its output to Chemicals and 10% to Machinery, and retains the rest. Machinery sells 40% to Chemicals and 40% to Fuels, and retains the rest.
(a) [5 pts] Construct the exchange table for this economy (columns: output from a sector; rows: purchased by a sector). Enter decimals.
| from Chem. | from Fuels | from Mach. | Purchased by |
|---|---|---|---|
| Chemicals & Metals | |||
| Fuels & Power | |||
| Machinery |
(b) [5 pts] Let \(p_C,p_F,p_M\) be the prices of the outputs of the three sectors. Write the system of equations that leads to prices at which each sector's income matches its expenses (one equation per row of the table), and write the augmented matrix that can be row reduced to find these prices.
(c) [5 pts] Find a set of equilibrium prices when the price of the Machinery output is 100 units. Show your row reduction or substitution; round final values to two decimal places, and check one of the balance equations with your numbers.