Linear Systems Workshop, linear algebra I lesson

Three measurements of three unknown readings sound like enough to pin the readings down. But if one measurement repeats another with every coefficient doubled, it adds nothing new when its recorded value is doubled too, and it makes the system impossible when it is not. This lesson practices deciding what a system determines before choosing a method, then describing every solution, treating a coefficient that can make a pivot vanish as its own case, keeping track of row swaps and confirming each answer in the original equations. Throughout, a tuple such as $(1, 2, 2)$ stands for a column vector.

Key terms

Classifying a system before solving

Definition To classify a linear system $A\mathbf{x} = \mathbf{b}$ of $m$ equations in $n$ unknowns is to decide, before computing any solution, whether it has no solution, exactly one, or infinitely many. Reduce the augmented matrix $[A \mid \mathbf{b}]$ to an echelon form by row operations, which do not change the solution set. If some row is an inconsistent row $[0 \ \cdots \ 0 \mid c]$ with $c \ne 0$ , which reads $0 = c$ , the system is inconsistent. Otherwise it is consistent, and it has exactly one solution when every column of $A$ is a pivot column and infinitely many when some column of $A$ has no pivot, with one free variable for each such column. Each row holds at most one pivot, so a system with fewer equations than unknowns never has exactly one solution. For a square matrix, $n$ pivots means that $A$ is invertible and that $\mathbf{x} = A^{-1}\mathbf{b}$ is the only solution for every $\mathbf{b}$ . With fewer than $n$ pivots there is no inverse, and each $\mathbf{b}$ gives either no solution or infinitely many.

In plain words Find out what the equations can determine before choosing how to solve them. An echelon form answers that question, and the answer tells you whether to look for one point, a whole family of points or a contradiction.

Example Consider the system

\begin{aligned} x + 2y - z &= 1 \\ 2x + 4y - 2z &= 2 \\ y + z &= 2 \end{aligned}

with coefficient matrix $A$ and augmented matrix

\left[\begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 2 \end{array}\right].

The operation $R_2 \to R_2 - 2R_1$ turns the second row into a row of zeros, and swapping $R_2$ and $R_3$ gives the echelon form

\left[\begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{array}\right].

There is no inconsistent row, the pivots sit in the $x$ and $y$ columns, and the $z$ column has none. The system is consistent with one free variable, so it has infinitely many solutions. The square matrix $A$ has only two pivots, so it has no inverse, and the answer has to be a family rather than a single point.

Redundant equation

Definition An equation of a linear system is redundant if it is a linear combination of the other equations, meaning that its row of $[A \mid \mathbf{b}]$ , right-hand side included, is a linear combination of the other rows. Every solution of the other equations then satisfies it, so deleting it leaves the solution set unchanged, and every echelon form of $[A \mid \mathbf{b}]$ has a zero row. For a fixed coefficient matrix $A$ , a right-hand side $\mathbf{b}$ is inconsistent when $A\mathbf{x} = \mathbf{b}$ has no solution, that is, when $\mathbf{b}$ is not a linear combination of the columns of $A$ . This happens exactly when some combination of the equations cancels every coefficient on the left but leaves a nonzero number on the right, so that it reads $0 = c$ with $c \ne 0$ . Elimination then produces a row $[0 \ \cdots \ 0 \mid d]$ with $d \ne 0$ .

In plain words A redundant equation repeats information the other equations already carry, so three equations may hold only two independent facts. When the left sides repeat each other but the recorded values do not repeat in the same way, the equations contradict each other, and no choice of the unknowns satisfies them all.

Example In the system above, the second equation is twice the first on both sides, so it is redundant, and the system has the same solutions as the pair $x + 2y - z = 1$ and $y + z = 2$ . Redundancy need not be a multiple of a single equation. In the system $x + y = 2$ , $y = 1$ , $x + 2y = 3$ , the third equation is the sum of the first two. Now return to the first system, keep its matrix $A$ and change only the second right side from $2$ to $3$ , so that $\mathbf{b} = (1, 3, 2)$ . Twice the first left side is still the second left side, and subtracting twice the first equation from the second gives

0x + 0y + 0z = 3 - 2 = 1.

No choice of $x$ , $y$ and $z$ makes $0 = 1$ true, so this right-hand side is inconsistent. The vector $(1, 3, 2)$ is not a combination of the columns of $A$ , and no solution exists.

Complete solution family

Definition Let $A\mathbf{x} = \mathbf{b}$ be a consistent system. Its complete solution family is the set of all its solutions, written with real parameters $t_1, \dots, t_k$ , one for each free variable, as

\mathbf{x} = \mathbf{x}_p + t_1\mathbf{v}_1 + \cdots + t_k\mathbf{v}_k,

where $\mathbf{x}_p$ is a particular solution and each $\mathbf{v}_i$ solves the homogeneous system $A\mathbf{v} = \mathbf{0}$ . Setting the free variables equal to the parameters and solving for the pivot variables by back-substitution produces such a family. A proposed family is complete when two statements hold. Every choice of the parameters gives a solution, and every solution comes from some choice of the parameters. When there are no free variables, the family is the single point $\mathbf{x}_p$ .

In plain words Report every set of values the equations allow, not just one that works. The particular solution is one point that fits, and the homogeneous directions are the changes to the unknowns that the equations cannot detect.

Example For the first system, with $\mathbf{b} = (1, 2, 2)$ , the free variable is $z$ , so set $z = t$ . The equation $y + z = 2$ gives $y = 2 - t$ , and the first equation gives $x = 1 - 2(2 - t) + t = -3 + 3t$ . So

\begin{gathered} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} -3 \\ 2 \\ 0 \end{bmatrix} + t\begin{bmatrix} 3 \\ -1 \\ 1 \end{bmatrix}, \\[0.4em] t \in \mathbb{R}. \end{gathered}

The particular solution $\mathbf{x}_p = (-3, 2, 0)$ gives $A\mathbf{x}_p = (1, 2, 2)$ , and the direction $\mathbf{v} = (3, -1, 1)$ gives $A\mathbf{v} = \mathbf{0}$ , so every value of $t$ gives a solution. Conversely, take any solution and call its third coordinate $t$ . The third equation forces $y = 2 - t$ , and then the first forces $x = -3 + 3t$ , so the solution lies in the family. The values $t = 0, 1, 2$ give $(-3, 2, 0)$ , $(0, 1, 1)$ and $(3, 0, 2)$ , three points on one line that $A$ sends to the same output $(1, 2, 2)$ .

Exceptional coefficient

Definition Suppose some coefficients of a linear system are given expressions in a real parameter $a$ , so that each value of $a$ gives its own system. A value of $a$ is exceptional when an expression in $a$ that elimination would divide by, usually a pivot, equals zero there. Case analysis splits the work in two. Where the divisor is nonzero, divide and obtain a formula valid for all those values. At each exceptional value, substitute it into the equations as they stood before the division and classify that system on its own, since the formula says nothing there. At an exceptional value the coefficient matrix can lose a pivot, and then the right-hand side decides between no solution and infinitely many.

In plain words A formula with $a - 1$ in a denominator was derived only for $a \ne 1$ , so it says nothing about what happens at $a = 1$ . Branch before you divide, and settle each excluded value with the equations themselves.

Example Take the system $x + y = 3$ and $x + ay = 1$ . The operation $R_2 \to R_2 - R_1$ divides by nothing and gives $(a - 1)y = -2$ . If $a \ne 1$ , division is allowed, and

\begin{gathered} y = -\frac{2}{a - 1}, \\[0.4em] x = 3 - y = \frac{3a - 1}{a - 1}. \end{gathered}

At $a = 3$ this gives $(4, -1)$ , and indeed $4 - 1 = 3$ and $4 + 3(-1) = 1$ . At $a = 1$ the equation $(a - 1)y = -2$ reads $0y = -2$ , so there is no solution, and the original equations agree, since $x + y$ cannot equal both $3$ and $1$ . If the second right side were $3$ instead of $1$ , the same value $a = 1$ would make the two equations identical, and every pair $(3 - t, t)$ with $t$ real would be a solution. The exceptional value stays the same, but the verdict there depends on the right-hand side.

Tracking a row swap

Definition When elimination exchanges rows of a square matrix $A$ , the final row order is recorded in a permutation matrix $P$ , the identity matrix with its rows in that order, and the factorization reads $PA = LU$ , where $L$ is lower triangular with ones on its diagonal and $U$ is upper triangular. If a swap happens after some multipliers are already stored, those stored multipliers in $L$ move with their rows. Partial pivoting chooses each pivot as an entry of largest absolute value in the current column, among the current row and the rows below it. For an invertible $A$ , suitable row exchanges always make every pivot nonzero, so $U$ has no zero on its diagonal. Then $A\mathbf{x} = \mathbf{b}$ is solved by applying the same permutation to the right-hand side and solving $LU\mathbf{x} = P\mathbf{b}$ in two steps, forward substitution for $L\mathbf{w} = P\mathbf{b}$ and then back-substitution for $U\mathbf{x} = \mathbf{w}$ . A swap reorders equations, not unknowns, so $\mathbf{x}$ comes out in the original variable order.

In plain words A row swap moves an equation together with its right side. The permutation is part of the record, and it has to act on $\mathbf{b}$ exactly as it acted on the rows of $A$ .

Example Let

\begin{gathered} K = \begin{bmatrix} 0 & 1 & 2 \\ 2 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}, \\[0.4em] \mathbf{b} = \begin{bmatrix} 0 \\ 3 \\ 2 \end{bmatrix}. \end{gathered}

The first column holds $0$ , $2$ and $1$ , so partial pivoting swaps $R_1$ and $R_2$ , giving the original rows in the order $2, 1, 3$ . The new second row already has $0$ in the first column, so its multiplier is $0$ . The third row has multiplier $\tfrac{1}{2}$ , and $R_3 \to R_3 - \tfrac{1}{2}R_1$ leaves a third row with entries $0$ , $\tfrac{1}{2}$ , $\tfrac{1}{2}$ . In the second column the candidates are $1$ and $\tfrac{1}{2}$ , so no swap is needed. The multiplier is $\tfrac{1}{2}$ , and $R_3 \to R_3 - \tfrac{1}{2}R_2$ leaves entries $0$ , $0$ , $-\tfrac{1}{2}$ . Hence $PK = LU$ with

\begin{gathered} P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \\[0.4em] L = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \tfrac{1}{2} & \tfrac{1}{2} & 1 \end{bmatrix}, \\[0.4em] U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & -\tfrac{1}{2} \end{bmatrix}. \end{gathered}

The same swap gives $P\mathbf{b} = (3, 0, 2)$ . Forward substitution in $L\mathbf{w} = P\mathbf{b}$ gives $w_1 = 3$ , $w_2 = 0$ and $\tfrac{1}{2}(3) + \tfrac{1}{2}(0) + w_3 = 2$ , so $w_3 = \tfrac{1}{2}$ . Back-substitution in $U\mathbf{x} = \mathbf{w}$ gives $-\tfrac{1}{2}z = \tfrac{1}{2}$ , so $z = -1$ , then $y + 2z = 0$ , so $y = 2$ , and finally $2x + y + z = 3$ , so $x = 1$ . The solution is $(1, 2, -1)$ in the original order $x, y, z$ .

Checking the original equations

Definition Checking the original equations means substituting a proposed answer into every equation of the system as it was first given, before any row operation, swap, deletion or division. For a solution family, the parameter stays a letter, so one computation covers every parameter value. For a formula that depends on a coefficient parameter, the check is done symbolically under the same nonzero condition, and each exceptional value is checked on its own. When a factorization $PA = LU$ is used, comparing the product $LU$ with $PA$ checks the stored factors, which is a different question from whether the computed $\mathbf{x}$ solves $A\mathbf{x} = \mathbf{b}$ . A passing check shows that the proposed points are solutions. It does not show that none are missing, which needs the converse argument of a complete solution family.

In plain words Reduced, reordered and triangular systems are working copies, and a slip made while producing them stays invisible from inside them. The original equations are the question that was actually asked, so they get the last word.

Example For $K$ and $\mathbf{b}$ above, the vector $(1, 2, -1)$ gives $y + 2z = 2 - 2 = 0$ , $2x + y + z = 2 + 2 - 1 = 3$ and $x + y + z = 1 + 2 - 1 = 2$ , so all three original equations hold. The factors pass their own check as well. The first two rows of $LU$ are the first two rows of $U$ , which are rows $2$ and $1$ of $K$ . The third row of $LU$ is $\tfrac{1}{2}$ times the first row of $U$ plus $\tfrac{1}{2}$ times its second row plus its third row. Its entries are $1$ , $1$ , $1$ , exactly the third row of $K$ , so $PK = LU$ . To see why the original check matters, suppose the permutation is forgotten and $L\mathbf{w} = \mathbf{b}$ is solved instead. That gives $\mathbf{w} = (0, 3, \tfrac{1}{2})$ and then the candidate $(-2, 5, -1)$ , which satisfies $U\mathbf{x} = \mathbf{w}$ exactly. Yet the first original equation gives $y + 2z = 5 - 2 = 3$ , not $0$ , so the candidate is wrong.

Check yourself

Classify the system below and find every solution. One of its equations is redundant. Does that mean it has infinitely many solutions?

\begin{aligned} x + 2y &= 3 \\ 2x + 4y &= 6 \\ x - y &= 0 \end{aligned}

Show the answer

The second equation is twice the first, right side included, so it is redundant. The operations $R_2 \to R_2 - 2R_1$ and $R_3 \to R_3 - R_1$ , followed by a swap of $R_2$ and $R_3$ , give

\left[\begin{array}{cc|c} 1 & 2 & 3 \\ 0 & -3 & -3 \\ 0 & 0 & 0 \end{array}\right].

There is no inconsistent row, and both columns of the coefficient matrix are pivot columns, so the solution is unique despite the redundant equation. Back-substitution gives $y = 1$ and then $x = 3 - 2 = 1$ . The original equations check, since $1 + 2 = 3$ , $2 + 4 = 6$ and $1 - 1 = 0$ . A redundant equation only means that one equation carries no new information. For a consistent system, uniqueness depends on whether every unknown gets a pivot.

Factor the coefficient matrix $A$ of the system below as $PA = LU$ using partial pivoting, then solve the system and check the original equations. If a swap is needed after elimination has started, what happens to the multipliers already stored in $L$ ?

\begin{aligned} 4x + 4y + 4z &= 4 \\ 2x + 2y + 3z &= 3 \\ x + 3y + 2z &= 0 \end{aligned}

Show the answer

In the first column the candidates are $4$ , $2$ and $1$ , so the pivot $4$ stays in the first row. The multipliers are $\tfrac{1}{2}$ for the second row and $\tfrac{1}{4}$ for the third, and the operations $R_2 \to R_2 - \tfrac{1}{2}R_1$ and $R_3 \to R_3 - \tfrac{1}{4}R_1$ leave a second row with entries $0$ , $0$ , $1$ and a third row with entries $0$ , $2$ , $1$ . In the second column the candidates are now $0$ and $2$ , so rows $2$ and $3$ swap, and their stored multipliers swap with them. The new second row carries $\tfrac{1}{4}$ and the new third row carries $\tfrac{1}{2}$ . The new third row already has $0$ in the second column, so its second multiplier is $0$ . The final row order is $1, 3, 2$ , and

\begin{gathered} P = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, \\[0.4em] L = \begin{bmatrix} 1 & 0 & 0 \\ \tfrac{1}{4} & 1 & 0 \\ \tfrac{1}{2} & 0 & 1 \end{bmatrix}, \\[0.4em] U = \begin{bmatrix} 4 & 4 & 4 \\ 0 & 2 & 1 \\ 0 & 0 & 1 \end{bmatrix}. \end{gathered}

The right side $\mathbf{b} = (4, 3, 0)$ becomes $P\mathbf{b} = (4, 0, 3)$ . Forward substitution gives $w_1 = 4$ , then $\tfrac{1}{4}(4) + w_2 = 0$ , so $w_2 = -1$ , and $\tfrac{1}{2}(4) + w_3 = 3$ , so $w_3 = 1$ . Back-substitution gives $z = 1$ , then $2y + 1 = -1$ , so $y = -1$ , and $4x - 4 + 4 = 4$ , so $x = 1$ . The original equations give $4 - 4 + 4 = 4$ , $2 - 2 + 3 = 3$ and $1 - 3 + 2 = 0$ , so the solution is $(1, -1, 1)$ . If the multipliers stayed behind during the swap, the second row of $LU$ would have entries $2$ , $4$ , $3$ , while the second row of $PA$ is $1$ , $3$ , $2$ . Solving with that wrong $L$ gives $(1, -2, 2)$ , which fails the last two original equations, for instance $2 - 4 + 6 = 4$ rather than $3$ .

For which real numbers $k$ does the system below have no solution, exactly one solution or infinitely many? Give the solution when it is unique. A student cancels a common factor and reports $x = 4/(2 + k)$ and $y = 2/(2 + k)$ for every $k \ne -2$ . What does that miss?

\begin{aligned} x + ky &= 2 \\ kx + 4y &= 4 \end{aligned}

Show the answer

The operation $R_2 \to R_2 - kR_1$ divides by nothing, so it is valid for every $k$ . It gives

\begin{aligned} (4 - k^2)\,y &= 4 - 2k, \\[0.4em] (2 - k)(2 + k)\,y &= 2(2 - k). \end{aligned}

If $k \ne 2$ and $k \ne -2$ , dividing by $(2 - k)(2 + k)$ is allowed, and the solution is unique,

\begin{gathered} y = \frac{2}{2 + k}, \\[0.4em] x = 2 - ky = \frac{4}{2 + k}. \end{gathered}

It checks in the original equations, because

\begin{aligned} x + ky &= \frac{4 + 2k}{2 + k} = 2, \\[0.4em] kx + 4y &= \frac{4k + 8}{2 + k} = 4. \end{aligned}

At $k = -2$ the reduced equation reads $0 = 8$ , so there is no solution. Indeed the original equations become $x - 2y = 2$ and $-2x + 4y = 4$ , and the second says $x - 2y = -2$ . At $k = 2$ the reduced equation reads $0 = 0$ , the second equation $2x + 4y = 4$ is twice the first, and every pair $(2 - 2t, t)$ with $t$ real is a solution. The student’s formula gives $(1, \tfrac{1}{2})$ at $k = 2$ , which is only the point $t = \tfrac{1}{2}$ of that family, so it misses infinitely many solutions there. Canceling $2 - k$ was valid only under the condition $k \ne 2$ .

Linear Systems Workshop

Key terms

Classifying a system before solving

Redundant equation

Complete solution family

Exceptional coefficient

Tracking a row swap

Checking the original equations

Check yourself

How this lesson connects

Builds on