Chapter 1: Linear SystemsContent check — Linear Algebra, Chapter 1: Linear Systems

Gauss’s Method

$$\stackrel{-(1/2){\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccc}\hfill 2x& +& \hfill 3y& =& \hfill 13\\ \hfill & -& \hfill (5/2)y& =& \hfill -15/2\end{array}$$

gives that the solution is $y=3$ and $x=2$⁠.

Gauss’s Method here

$$\underset{\begin{array}{c}{\rho }_1+{\rho }_3\end{array}}{\overset{-3{\rho }_1+{\rho }_2}{⟶}}\begin{array}{ccccccc}\hfill x& & \hfill & -& \hfill z& =& \hfill 0\\ \hfill & & \hfill y& +& \hfill 3z& =& \hfill 1\\ \hfill & & \hfill y& & \hfill & =& \hfill 4\end{array}\stackrel{-{\rho }_2+{\rho }_3}{⟶}\begin{array}{ccccccc}\hfill x& & \hfill & -& \hfill z& =& \hfill 0\\ \hfill & & \hfill y& +& \hfill 3z& =& \hfill 1\\ \hfill & & \hfill & & \hfill -3z& =& \hfill 3\end{array}$$

gives $x=-1$⁠, $y=4$⁠, and $z=-1$⁠.

If a system has a contradictory equation then it has no solution. Otherwise, if there are any variables that are not leading a row then it has infinitely many solution. In the final case, where there is no contradictory equation and every variable leads some row, it has a unique solution.

Unique solution

Infinitely many solutions

Infinitely many solutions

No solution

Infinitely many solutions

Infinitely many solutions

No solution

Infinitely many solutions

No solution

Unique solution

Gaussian reduction

$$\stackrel{-(1/2){\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccc}\hfill 2x& +& \hfill 2y& =& \hfill 5\\ \hfill & & \hfill -5y& =& \hfill -5/2\end{array}$$

shows that $y=1/2$ and $x=2$ is the unique solution.

Gauss’s Method

$$\stackrel{{\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccc}\hfill -x& +& \hfill y& =& \hfill 1\\ \hfill & & \hfill 2y& =& \hfill 3\end{array}$$

gives $y=3/2$ and $x=1/2$ as the only solution.

Row reduction

$$\stackrel{-{\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccccc}\hfill x& -& \hfill 3y& +& \hfill z& =& \hfill 1\\ \hfill & & \hfill 4y& +& \hfill z& =& \hfill 13\end{array}$$

shows, because the variable $z$ is not a leading variable in any row, that there are many solutions.

Row reduction

$$\stackrel{-3{\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccc}\hfill -x& -& \hfill y& =& \hfill 1\\ \hfill & & \hfill 0& =& \hfill -1\end{array}$$

shows that there is no solution.

Gauss’s Method

$$\begin{array}{cc}\hfill \stackrel{{\rho }_1\leftrightarrow {\rho }_4}{⟶}\begin{array}{ccccccc}\hfill x& +& \hfill y& -& \hfill z& =& \hfill 10\\ \hfill 2x& -& \hfill 2y& +& \hfill z& =& \hfill 0\\ \hfill x& & \hfill & +& \hfill z& =& \hfill 5\\ \hfill & & \hfill 4y& +& \hfill z& =& \hfill 20\end{array}& \underset{\begin{array}{c}-{\rho }_1+{\rho }_3\end{array}}{\overset{-2{\rho }_1+{\rho }_2}{⟶}}\begin{array}{ccccccc}\hfill x& +& \hfill y& -& \hfill z& =& \hfill 10\\ \hfill & & \hfill -4y& +& \hfill 3z& =& \hfill -20\\ \hfill & & \hfill -y& +& \hfill 2z& =& \hfill -5\\ \hfill & & \hfill 4y& +& \hfill z& =& \hfill 20\end{array}\hfill \\ \hfill & \underset{\begin{array}{c}{\rho }_2+{\rho }_4\end{array}}{\overset{-(1/4){\rho }_2+{\rho }_3}{⟶}}\begin{array}{ccccccc}\hfill x& +& \hfill y& -& \hfill z& =& \hfill 10\\ \hfill & & \hfill -4y& +& \hfill 3z& =& \hfill -20\\ \hfill & & \hfill & & \hfill (5/4)z& =& \hfill 0\\ \hfill & & \hfill & & \hfill 4z& =& \hfill 0\end{array}\hfill \end{array}$$

gives the unique solution $(x,y,z)=(\mathrm{5,5,0})$⁠.

Here Gauss’s Method gives

$$\begin{array}{cc}\hfill & \underset{\begin{array}{c}-2{\rho }_1+{\rho }_4\end{array}}{\overset{-(3/2){\rho }_1+{\rho }_3}{⟶}}\begin{array}{ccccccccc}\hfill 2x& \phantom{+}& \hfill & +& \hfill z& +& \hfill w& =& \hfill 5\\ \hfill & & \hfill y& & \hfill & -& \hfill w& =& \hfill -1\\ \hfill & & \hfill & -& \hfill (5/2)z& -& \hfill (5/2)w& =& \hfill -15/2\\ \hfill & & \hfill y& & \hfill & -& \hfill w& =& \hfill -1\end{array}\hfill \\ \hfill & \stackrel{-{\rho }_2+{\rho }_4}{⟶}\begin{array}{ccccccccc}\hfill 2x& \phantom{+}& \hfill & +& \hfill z& +& \hfill w& =& \hfill 5\\ \hfill & & \hfill y& & \hfill & -& \hfill w& =& \hfill -1\\ \hfill & & \hfill & -& \hfill (5/2)z& -& \hfill (5/2)w& =& \hfill -15/2\\ \hfill & & \hfill & & \hfill & & \hfill 0& =& \hfill 0\end{array}\hfill \end{array}$$

which shows that there are many solutions.

Gauss’s Method

$$\begin{array}{cc}\hfill \begin{array}{ccccccc}\hfill x& +& \hfill y& +& \hfill z& =& \hfill 5\\ \hfill x& -& \hfill y& & \hfill & =& \hfill 0\\ \hfill & & \hfill y& +& \hfill 2z& =& \hfill 7\end{array}& \stackrel{-{\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccccc}\hfill x& +& \hfill y& +& \hfill z& =& \hfill 5\\ \hfill & & \hfill -2y& -& \hfill z& =& \hfill -5\\ \hfill & & \hfill y& +& \hfill 2z& =& \hfill 7\end{array}\hfill \\ \hfill & \stackrel{(1/2){\rho }_2+{\rho }_3}{⟶}\begin{array}{ccccccc}\hfill x& +& \hfill y& +& \hfill z& =& \hfill 5\\ \hfill & & \hfill -2y& -& \hfill 1& =& \hfill -5\\ \hfill & & \hfill & & \hfill (3/2)z& =& \hfill 9/2\end{array}\hfill \end{array}$$

followed by back-substitution gives $x=1$⁠, $y=1$⁠, and $z=3$⁠.

Here Gauss’s Method

$$\begin{array}{cc}\hfill \begin{array}{ccccccc}\hfill 3x& & \hfill & +& \hfill z& =& \hfill 7\\ \hfill x& -& \hfill y& +& \hfill 3z& =& \hfill 4\\ \hfill x& +& \hfill 2y& -& \hfill 5z& =& \hfill -1\end{array}& \underset{\begin{array}{c}-(1/3){\rho }_1+{\rho }_3\end{array}}{\overset{-(1/3){\rho }_1+{\rho }_2}{⟶}}\begin{array}{ccccccc}\hfill 3x& & \hfill & +& \hfill z& =& \hfill 7\\ \hfill & & \hfill -y& +& \hfill (8/3)z& =& \hfill 5/3\\ \hfill & & \hfill 2y& -& \hfill (16/3)z& =& \hfill -(10/3)\end{array}\hfill \\ \hfill & \stackrel{2{\rho }_2+{\rho }_3}{⟶}\begin{array}{ccccccc}\hfill 3x& & \hfill & +& \hfill z& =& \hfill 7\\ \hfill & & \hfill -y& +& \hfill (8/3)z& =& \hfill 5/3\\ \hfill & & \hfill & & \hfill 0& =& \hfill 0\end{array}\hfill \end{array}$$

finds that the variable $z$ does not lead a row. There are infinitely many solutions.

The steps

$$\begin{array}{ccccccc}\hfill x& +& \hfill 3y& +& \hfill z& =& \hfill 0\\ \hfill -x& -& \hfill y& & \hfill & =& \hfill 2\\ \hfill -x& +& \hfill y& +& \hfill 2z& =& \hfill 8\end{array}\underset{\begin{array}{c}{\rho }_1+{\rho }_3\end{array}}{\overset{{\rho }_1+{\rho }_2}{⟶}}\begin{array}{ccccccc}\hfill x& +& \hfill 3y& +& \hfill z& =& \hfill 0\\ \hfill & & \hfill 2y& +& \hfill z& =& \hfill 2\\ \hfill & & \hfill 4y& +& \hfill 3z& =& \hfill 8\end{array}\stackrel{-2{\rho }_2+{\rho }_3}{⟶}\begin{array}{ccccccc}\hfill x& +& \hfill 3y& +& \hfill z& =& \hfill 0\\ \hfill & & \hfill 2y& +& \hfill z& =& \hfill 2\\ \hfill & & \hfill & & \hfill z& =& \hfill 4\end{array}$$

give $(x,y,z)=(-1,-\mathrm{1,4})$⁠.

From $x=1-3y$ we get that $2(1-3y)+y=-3$⁠, giving $y=1$⁠.

From $x=1-3y$ we get that $2(1-3y)+2y=0$⁠, leading to the conclusion that $y=1/2$⁠.

Users of this method must check any potential solutions by substituting back into all the equations.

Do the reduction

$$\stackrel{-3{\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccc}\hfill x& -& \hfill y& =& \hfill 1\\ \hfill & & \hfill 0& =& \hfill -3+k\end{array}$$

to conclude this system has no solutions if $k\ne 3$ and if $k=3$ then it has infinitely many solutions. It never has a unique solution.

Let $x=\sin \alpha$⁠, $y=\cos \beta$⁠, and $z=\tan \gamma$⁠:

$$\begin{array}{ccccccc}\hfill 2x& -& \hfill y& +& \hfill 3z& =& \hfill 3\\ \hfill 4x& +& \hfill 2y& -& \hfill 2z& =& \hfill 10\\ \hfill 6x& -& \hfill 3y& +& \hfill z& =& \hfill 9\end{array}\underset{\begin{array}{c}-3{\rho }_1+{\rho }_3\end{array}}{\overset{-2{\rho }_1+{\rho }_2}{⟶}}\begin{array}{ccccccc}\hfill 2x& -& \hfill y& +& \hfill 3z& =& \hfill 3\\ \hfill & & \hfill 4y& -& \hfill 8z& =& \hfill 4\\ \hfill & & \hfill & & \hfill -8z& =& \hfill 0\end{array}$$

gives $z=0$⁠, $y=1$⁠, and $x=2$⁠. Note that no $\alpha \in ℝ$ satisfies that $\sin \alpha =2$⁠.

Gauss’s Method

$$\underset{\begin{array}{c}-{\rho }_1+{\rho }_3\\ -2{\rho }_1+{\rho }_4\end{array}}{\overset{-3{\rho }_1+{\rho }_2}{⟶}}\begin{array}{ccccc}\hfill x& -& \hfill 3y& =& \hfill b_1\\ \hfill & & \hfill 10y& =& \hfill -3b_1+b_2\\ \hfill & & \hfill 10y& =& \hfill -b_1+b_3\\ \hfill & & \hfill 10y& =& \hfill -2b_1+b_4\end{array}\underset{\begin{array}{c}-{\rho }_2+{\rho }_4\end{array}}{\overset{-{\rho }_2+{\rho }_3}{⟶}}\begin{array}{ccccc}\hfill x& -& \hfill 3y& =& \hfill b_1\\ \hfill & & \hfill 10y& =& \hfill -3b_1+b_2\\ \hfill & & \hfill 0& =& \hfill 2b_1-b_2+b_3\\ \hfill & & \hfill 0& =& \hfill b_1-b_2+b_4\end{array}$$

shows that this system is consistent if and only if both $b_3=-2b_1+b_2$ and $b_4=-b_1+b_2$⁠.

Reduction

$$\begin{array}{cc}\hfill & \underset{\begin{array}{c}-{\rho }_1+{\rho }_3\end{array}}{\overset{-2{\rho }_1+{\rho }_2}{⟶}}\begin{array}{ccccccc}\hfill x_1& +& \hfill 2x_2& +& \hfill 3x_3& =& \hfill b_1\\ \hfill & & \hfill x_2& -& \hfill 3x_3& =& \hfill -2b_1+b_2\\ \hfill & & \hfill -2x_2& +& \hfill 5x_3& =& \hfill -b_1+b_3\end{array}\hfill \\ \hfill & \stackrel{2{\rho }_2+{\rho }_3}{⟶}\begin{array}{ccccccc}\hfill x_1& +& \hfill 2x_2& +& \hfill 3x_3& =& \hfill b_1\\ \hfill & & \hfill x_2& -& \hfill 3x_3& =& \hfill -2b_1+b_2\\ \hfill & & \hfill & & \hfill -x_3& =& \hfill -5b_1+2b_2+b_3\end{array}\hfill \end{array}$$

shows that each of $b_1$⁠, $b_2$⁠, and $b_3$ can be any real number — this system always has a unique solution.

This system with more unknowns than equations

$$\begin{array}{ccccccc}\hfill x& +& \hfill y& +& \hfill z& =& \hfill 0\\ \hfill x& +& \hfill y& +& \hfill z& =& \hfill 1\end{array}$$

has no solution.

Yes. For example, the fact that we can have the same reaction in two different flasks shows that twice any solution is another, different, solution (if a physical reaction occurs then there must be at least one nonzero solution).

Because $f(1)=2$⁠, $f(-1)=6$⁠, and $f(2)=3$ we get a linear system.

$$\begin{array}{ccccccc}\hfill 1a& +& \hfill 1b& +& \hfill c& =& \hfill 2\\ \hfill 1a& -& \hfill 1b& +& \hfill c& =& \hfill 6\\ \hfill 4a& +& \hfill 2b& +& \hfill c& =& \hfill 3\end{array}$$

Gauss’s Method

$$\underset{\begin{array}{c}-4{\rho }_1+{\rho }_3\end{array}}{\overset{-{\rho }_1+{\rho }_2}{⟶}}\begin{array}{ccccccc}\hfill a& +& \hfill b& +& \hfill c& =& \hfill 2\\ \hfill & & \hfill -2b& & \hfill & =& \hfill 4\\ \hfill & & \hfill -2b& -& \hfill 3c& =& \hfill -5\end{array}\stackrel{-{\rho }_2+{\rho }_3}{⟶}\begin{array}{ccccccc}\hfill a& +& \hfill b& +& \hfill c& =& \hfill 2\\ \hfill & & \hfill -2b& & \hfill & =& \hfill 4\\ \hfill & & \hfill & & \hfill -3c& =& \hfill -9\end{array}$$

shows that the solution is $f(x)=1x^2-2x+3$⁠.

Here $S_0=\{(\mathrm{1,1})\}$

$$\begin{array}{ccccc}\hfill x& +& \hfill y& =& \hfill 2\\ \hfill x& -& \hfill y& =& \hfill 0\end{array}\stackrel{0{\rho }_2}{⟶}\begin{array}{ccccc}\hfill x& +& \hfill y& =& \hfill 2\\ \hfill & & \hfill 0& =& \hfill 0\end{array}$$

while $S_1$ is a proper superset because it contains at least two points: $(\mathrm{1,1})$ and $(\mathrm{2,0})$⁠. In this example the solution set does not change.

$$\begin{array}{ccccc}\hfill x& +& \hfill y& =& \hfill 2\\ \hfill 2x& +& \hfill 2y& =& \hfill 4\end{array}\stackrel{0{\rho }_2}{⟶}\begin{array}{ccccc}\hfill x& +& \hfill y& =& \hfill 2\\ \hfill & & \hfill 0& =& \hfill 0\end{array}$$

Yes, by inspection the given equation results from $-{\rho }_1+{\rho }_2$⁠.

No. The pair $(\mathrm{1,1})$ satisfies the given equation. However, that pair does not satisfy the first equation in the system.

Yes. To see if the given row is $c_1{\rho }_1+c_2{\rho }_2$⁠, solve the system of equations relating the coefficients of $x$⁠, $y$⁠, $z$⁠, and the constants:

$$\begin{array}{ccccc}\hfill 2c_1& +& \hfill 6c_2& =& \hfill 6\\ \hfill c_1& -& \hfill 3c_2& =& \hfill -9\\ \hfill -c_1& +& \hfill c_2& =& \hfill 5\\ \hfill 4c_1& +& \hfill 5c_2& =& \hfill -2\end{array}$$

and get $c_1=-3$ and $c_2=2$⁠, so the given row is $-3{\rho }_1+2{\rho }_2$⁠.

If $a\ne 0$ then the solution set of the first equation is this.

$$\begin{array}{ccc}& \{(x,y)\in {ℝ}^2|x=(c-by)/a=(c/a)-(b/a)\cdot y\}& \text{(}\ast \text{)}\end{array}$$

Thus, given $y$ we can compute the associated $x$⁠. Taking $y=0$ gives the solution $(c/a,0)$⁠, and since the second equation $ax+dy=e$ is supposed to have the same solution set, substituting into it gives that $a(c/a)+d\cdot 0=e$⁠, so $c=e$⁠. Taking $y=1$ in ($\ast$⁠) gives $a((c-b)/a)+d\cdot 1=e$⁠, and so $b=d$⁠. Hence they are the same equation.

When $a=0$ the equations can be different and still have the same solution set: e.g., $0x+3y=6$ and $0x+6y=12$⁠.

We take three cases: that $a\ne 0$⁠, that $a=0$ and $c\ne 0$⁠, and that both $a=0$ and $c=0$⁠.

For the first, we assume that $a\ne 0$⁠. Then the reduction

$$\stackrel{-(c/a){\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccc}\hfill ax& +& \hfill by& =& \hfill j\\ \hfill & & \hfill (-(cb/a)+d)y& =& \hfill -(cj/a)+k\end{array}$$

shows that this system has a unique solution if and only if $-(cb/a)+d\ne 0$⁠; remember that $a\ne 0$ so that back substitution yields a unique $x$ (observe, by the way, that $j$ and $k$ play no role in the conclusion that there is a unique solution, although if there is a unique solution then they contribute to its value). But $-(cb/a)+d=(ad-bc)/a$ and a fraction is not equal to $0$ if and only if its numerator is not equal to $0$⁠. Thus, in this first case, there is a unique solution if and only if $ad-bc\ne 0$⁠.

In the second case, if $a=0$ but $c\ne 0$⁠, then we swap

$$\begin{array}{ccccc}\hfill cx& +& \hfill dy& =& \hfill k\\ \hfill & & \hfill by& =& \hfill j\end{array}$$

to conclude that the system has a unique solution if and only if $b\ne 0$ (we use the case assumption that $c\ne 0$ to get a unique $x$ in back substitution). But — where $a=0$ and $c\ne 0$ — the condition “⁠$b\ne 0$⁠” is equivalent to the condition “⁠$ad-bc\ne 0$⁠”. That finishes the second case.

Finally, for the third case, if both $a$ and $c$ are $0$ then the system

$$\begin{array}{ccccc}\hfill 0x& +& \hfill by& =& \hfill j\\ \hfill 0x& +& \hfill dy& =& \hfill k\end{array}$$

might have no solutions (if the second equation is not a multiple of the first) or it might have infinitely many solutions (if the second equation is a multiple of the first then for each $y$ satisfying both equations, any pair $(x,y)$ will do), but it never has a unique solution. Note that $a=0$ and $c=0$ gives that $ad-bc=0$⁠.

Recall that if a pair of lines share two distinct points then they are the same line. That’s because two points determine a line, so these two points determine each of the two lines, and so they are the same line.

Thus the lines can share one point (giving a unique solution), share no points (giving no solutions), or share at least two points (which makes them the same line).

For the reduction operation of multiplying ${\rho }_i$ by a nonzero real number $k$⁠, we have that $(s_1,\dots ,s_n)$ satisfies this system

$$\begin{array}{ccccccccc}\hfill a_{\mathrm{1,1}}{x}_1& +& \hfill a_{\mathrm{1,2}}{x}_2& +& \hfill \cdots & +& \hfill a_{1,n}{x}_n& =& \hfill d_1\\ \hfill & & \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill k{a}_{i,1}{x}_1& +& \hfill k{a}_{i,2}{x}_2& +& \hfill \cdots & +& \hfill k{a}_{i,n}{x}_n& =& \hfill k{d}_i\\ \hfill & & \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill a_{m,1}{x}_1& +& \hfill a_{m,2}{x}_2& +& \hfill \cdots & +& \hfill a_{m,n}{x}_n& =& \hfill d_m\end{array}$$

if and only if $a_{\mathrm{1,1}}{s}_1+$ $a_{\mathrm{1,2}}{s}_2+$ $\cdots +$ $a_{1,n}{s}_n=$ $d_1$ and … $k{a}_{i,1}{s}_1+$ $k{a}_{i,2}{s}_2+$ $\cdots +$ $k{a}_{i,n}{s}_n=$ $k{d}_i$ and … $a_{m,1}{s}_1+$ $a_{m,2}{s}_2+$ $\cdots +$ $a_{m,n}{s}_n=$ $d_m$ by the definition of ‘satisfies’. Because $k\ne 0$⁠, that’s true if and only if $a_{\mathrm{1,1}}{s}_1+$ $a_{\mathrm{1,2}}{s}_2+$ $\cdots +$ $a_{1,n}{s}_n=$ $d_1$ and … $a_{i,1}{s}_1+$ $a_{i,2}{s}_2+$ $\cdots +$ $a_{i,n}{s}_n=$ $d_i$ and … $a_{m,1}{s}_1+$ $a_{m,2}{s}_2+$ $\cdots +$ $a_{m,n}{s}_n=$ $d_m$ (this is straightforward canceling on both sides of the $i$⁠-th equation), which says that $(s_1,\dots ,s_n)$ solves

$$\begin{array}{ccccccccc}\hfill a_{\mathrm{1,1}}{x}_1& +& \hfill a_{\mathrm{1,2}}{x}_2& +& \hfill \cdots & +& \hfill a_{1,n}{x}_n& =& \hfill d_1\\ \hfill & & \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill a_{i,1}{x}_1& +& \hfill a_{i,2}{x}_2& +& \hfill \cdots & +& \hfill a_{i,n}{x}_n& =& \hfill d_i\\ \hfill & & \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill a_{m,1}{x}_1& +& \hfill a_{m,2}{x}_2& +& \hfill \cdots & +& \hfill a_{m,n}{x}_n& =& \hfill d_m\end{array}$$

as required.

For the combination operation $k{\rho }_i+{\rho }_j$⁠, the tuple $(s_1,\dots ,s_n)$ satisfies

$$\begin{array}{ccccccc}\hfill a_{\mathrm{1,1}}{x}_1& +& \hfill \cdots & +& \hfill a_{1,n}{x}_n& =& \hfill d_1\\ \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill a_{i,1}{x}_1& +& \hfill \cdots & +& \hfill a_{i,n}{x}_n& =& \hfill d_i\\ \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill (k{a}_{i,1}+a_{j,1})x_1& +& \hfill \cdots & +& \hfill (k{a}_{i,n}+a_{j,n})x_n& =& \hfill k{d}_i+d_j\\ \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill a_{m,1}{x}_1& +& \hfill \cdots & +& \hfill a_{m,n}{x}_n& =& \hfill d_m\end{array}$$

if and only if $a_{\mathrm{1,1}}{s}_1+\cdots +a_{1,n}{s}_n=d_1$ and … $a_{i,1}{s}_1+\cdots +a_{i,n}{s}_n=d_i$ and … $(k{a}_{i,1}+a_{j,1})s_1+$ $\cdots +$ $(k{a}_{i,n}+a_{j,n})s_n=$ $k{d}_i+$ $d_j$ and … $a_{m,1}{s}_1+$ $a_{m,2}{s}_2+$ $\cdots +$ $a_{m,n}{s}_n=$ $d_m$ again by the definition of ‘satisfies’. Subtract $k$ times the equation $i$ from equation $j$⁠. (Here is where we need $i\ne j$⁠; if $i=j$ then the two $d_i$⁠’s above are not equal.) The previous compound statement holds if and only if $a_{\mathrm{1,1}}{s}_1+\cdots +a_{1,n}{s}_n=d_1$ and … $a_{i,1}{s}_1+\cdots +a_{i,n}{s}_n=d_i$ and… $(k{a}_{i,1}+a_{j,1})s_1+$ $\cdots +$ $(k{a}_{i,n}+a_{j,n})s_n-$ $(k{a}_{i,1}{s}_1+\cdots +k{a}_{i,n}{s}_n)=$ $k{d}_i+$ $d_j-$ $k{d}_i$ and… $a_{m,1}{s}_1+\cdots +a_{m,n}{s}_n=d_m$⁠, which after cancellation says that $(s_1,\dots ,s_n)$ solves

$$\begin{array}{ccccccc}\hfill a_{\mathrm{1,1}}{x}_1& +& \hfill \cdots & +& \hfill a_{1,n}{x}_n& =& \hfill d_1\\ \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill a_{i,1}{x}_1& +& \hfill \cdots & +& \hfill a_{i,n}{x}_n& =& \hfill d_i\\ \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill a_{j,1}{x}_1& +& \hfill \cdots & +& \hfill a_{j,n}{x}_n& =& \hfill d_j\\ \hfill & & \hfill & & \hfill & ⋮& \hfill \\ \hfill a_{m,1}{x}_1& +& \hfill \cdots & +& \hfill a_{m,n}{x}_n& =& \hfill d_m\end{array}$$

as required.

Yes, this one-equation system:

$$0x+0y=0$$

is satisfied by every $(x,y)\in {ℝ}^2$⁠.

Yes. This sequence of operations swaps rows $i$ and $j$

$$\stackrel{{\rho }_i+{\rho }_j}{⟶}\stackrel{-{\rho }_j+{\rho }_i}{⟶}\stackrel{{\rho }_i+{\rho }_j}{⟶}\stackrel{-1{\rho }_i}{⟶}$$

so the row-swap operation is redundant in the presence of the other two.

Reverse a row swap ${\rho }_i\leftrightarrow {\rho }_j$ by swapping back ${\rho }_j\leftrightarrow {\rho }_i$⁠. Reverse the $k{\rho }_i$ step of multiplying $k\ne 0$ on both sides of a row by dividing through $(1/k){\rho }_i$⁠.

The row combination case is the nontrivial one. The operation $k{\rho }_i+{\rho }_j$ results in this $j$⁠-th row.

$$k\cdot a_{i,1}+a_{j,1}+\cdots +k\cdot a_{i,n}+a_{j,n}=k\cdot d_i+d_j$$

The $i$⁠-th row unchanged because of the $i\ne j$ restriction. Because the $i$⁠-th row is unchanged, the operation $-k{\rho }_i+{\rho }_j$ returns the $j$⁠-th row to its original state.

(Observe that the $i=j$ condition on the $k{\rho }_i+{\rho }_j$ is needed, or else this could happen

$$\begin{array}{ccccc}\hfill 3x& +& \hfill 2y& =& \hfill 7\end{array}\stackrel{2{\rho }_1+{\rho }_1}{⟶}\begin{array}{ccccc}\hfill 9x& +& \hfill 6y& =& \hfill 21\end{array}\stackrel{-2{\rho }_1+{\rho }_1}{⟶}\begin{array}{ccccc}\hfill -9x& -& \hfill 6y& =& \hfill -21\end{array}$$

and so the result wouldn’t hold.)

Let $p$⁠, $n$⁠, and $d$ be the number of pennies, nickels, and dimes. For variables that are real numbers, this system

$$\begin{array}{ccccccc}\hfill p& +& \hfill n& +& \hfill d& =& \hfill 13\\ \hfill p& +& \hfill 5n& +& \hfill 10d& =& \hfill 83\end{array}\stackrel{-{\rho }_1+{\rho }_2}{⟶}\begin{array}{ccccccc}\hfill p& +& \hfill n& +& \hfill d& =& \hfill 13\\ \hfill & & \hfill 4n& +& \hfill 9d& =& \hfill 70\end{array}$$

has more than one solution; in fact, it has infinitely many of them. However, it has a limited number of solutions in which $p$⁠, $n$⁠, and $d$ are non-negative integers. Running through $d=0$⁠, …, $d=8$ shows that $(p,n,d)=(\mathrm{3,4,6})$ is the only solution using natural numbers.

Solving the system

$$\begin{array}{ccccc}\hfill (1/3)(a+b+c)& +& \hfill d& =& \hfill 29\\ \hfill (1/3)(b+c+d)& +& \hfill a& =& \hfill 23\\ \hfill (1/3)(c+d+a)& +& \hfill b& =& \hfill 21\\ \hfill (1/3)(d+a+b)& +& \hfill c& =& \hfill 17\end{array}$$

we obtain $a=12$⁠, $b=9$⁠, $c=3$⁠, $d=21$⁠. Thus the second item, 21, is the correct answer.