> [!Proposition] Proposition (Number of solutions to linear system) > Let $(A\mid \underline{b})$ be a matrix in [[Reduced Row Echelon Form for Real Matrix|RREF]] which represents a linear system $A\underline{x}=\underline{b}$ of $m$ equations in $n$ variables. Then: > 1. The system has no solutions iff the last non-zero row of $(A \mid \underline{b})$ is $\begin{pmatrix}0 & 0 &\dots &0 \mid 1 \end{pmatrix}.$ > 2. The system has a unique solution iff the non-zero rows of $A$ form the identity matrix $I_{n}$. In particular, this case is only possible if $m \geq n$ (i.e. more equations than variables/ long matrix). > 3. The system has infinitely many solutions iff $(A\mid b)$ has as many non-zero rows as $A$, and there is at least one column of $A$ that doesn't contains a pivot. The set of solutions can be described with $k$ parameters, where $k$ is the number of columns not containing a pivot. *Proof*. If $(A\mid \underline{b})$ contains the row $\begin{pmatrix}0 & 0&\dots&0\mid 1 \end{pmatrix}$ then the system is inconsistent as no $\underline{x}$ satisfies $0x_{1}+0x_{2}+\dots+0x_{n}=1.$ Since $(A \mid \underline{b})$ is in RREF, this is the only way in which $(A \mid \underline{b})$ can have more non-zero rows than $A$. We will show that whenever $(A \mid \underline{b})$ has as many non-zero rows as $A$ then the system $(A \mid \underline{b})$ is consistent. Suppose $(A \mid \underline{b})$ and $A$ have $r$ non-zero rows, so that there are $r$ pivots within these rows and we have $k=n-r$ columns without pivots. By reordering the numbers of the variables $x_{1},\dots,x_{n}$ if necessary, we can assume that the pivots appear in the first $r$ columns. So, ignoring any zero rows and remembering that the system is in reduced row echelon form, the system corresponds to the $r$ equations $\begin{aligned} x_1+a_{1(r+1)}x_{r+1}+\cdots+a_{1n}x_n &=b_{1} \\ x_2+a_{2(r+1)}x_{r+1}+\cdots+a_{2n}x_n &=b_{2} \\ & \vdots\\ x_r+a_{r(r+1)}x_{r+1}+\cdots+a_{rn}x_n &=b_{r} \end{aligned}$If we assign $x_{r+1},\dots,x_{n}$ the $k$ parameters $s_{r+1},\dots,s_{n}$, then we can read off from the $r$ equations the values for $x_{1},x_{2},\dots,x_{r}$: $\begin{aligned} x_{1}& =b_1-a_{1(r+1)}s_{r+1}-\cdots-a_{1n}s_n \\ x_{2}& =b_2-a_{2(r+1)}s_{r+1}-\cdots-a_{2n}s_n \\&\vdots\\ x_{r}& =b_r-a_{r(r+1)}s_{r+1}-\cdots-a_{rn}s_n \end{aligned}$So for any values of parameters, we have a solution $\underline{x}=(x_{1},\dots,x_{n})$. Thus we see that we have an infinite set of solutions associated with $k=n-r$ independent parameters when $n > r$, and a unique solution when $n = r$ (in which case the non-zero rows of $A$ are the [[Real Identity Matrix|identity matrix]] $I_{n}$).