Linear Systems, Elimination, and LU Factorization

A system asks which inputs satisfy all constraints

A linear equation in unknowns $x_1,\ldots,x_n$ has the form

$$a_1x_1+\cdots+a_nx_n=b,$$

with known coefficients and right-hand side. Unknowns occur only to the first power, not multiplied together, in denominators, or inside nonlinear functions. Thus $2x-y=3$ is linear, while $xy=3$ and $x^2+y=1$ are not. A zero coefficient may make an unknown absent from an equation.

A system requires the same unknown values to satisfy several equations simultaneously. The matrix form $A\mathbf x=\mathbf b$ has two complementary readings: each row is a constraint, while the columns are vectors whose combination must produce $\mathbf b$.

ExampleIntersecting, coincident, and parallel lines

The equation $x+y=2$ describes a line. Adding $x-y=0$ gives their unique intersection $(1,1)$.

Replacing the second equation by $2x+2y=4$ adds no constraint; every $(t,2-t)$ is a solution. Replacing it by $2x+2y=5$ produces a contradiction and no solution.

Counting equations and unknowns therefore gives only a first indication. Independence of constraints and compatibility of right-hand sides determine the answer.

Elimination reorganizes information

Elimination does not begin by guessing every unknown. It reorganizes constraints until dependent variables, free choices, or contradictions become visible. The expressions change while the solution set must remain fixed.

We first derive a system from conservation and follow its elimination in full. Then we extract the general algorithm and explain how LU records the work for reuse.

Conservation does not determine every traffic flow

Consider junctions $A,B,C,D$ with the following internal roads. Each $x_i$ measures vehicles per common unit of time along its arrow.

Road	Direction
$x_1$	$D\to B$
$x_2$	$A\to B$
$x_3$	$C\to A$
$x_4$	$C\to D$
$x_5$	$B\to C$

Assume no accumulation at a junction during the measurement period. External measurements give net outward flow $45$ at $B$, net inward flow $45$ at $C$, net inward flow $10$ at $A$, and net outward flow $10$ at $D$. These internal roads and external balances define the network we will model [1][1] X. Yang, “ENG1005 Week 2: Traffic Flow, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W2.tex.

Writing the balances in the order $B,C,A,D$ gives

$$\begin{cases} x_1+x_2-x_5=45,\\ x_3+x_4-x_5=45,\\ -x_2+x_3=-10,\\ -x_1+x_4=10. \end{cases}$$

Each equation is valid, but four equations do not necessarily provide four independent constraints.

Why row operations preserve solutions

Collect coefficients and right-hand sides in an augmented matrix:

$$[A\mid\mathbf b]= \left[\begin{array}{rrrrr|r} 1&1&0&0&-1&45\\ 0&0&1&1&-1&45\\ 0&-1&1&0&0&-10\\ -1&0&0&1&0&10 \end{array}\right].$$

Elementary row operations swap two rows, multiply a row by a nonzero scalar, or add a multiple of another row to it. Each operation has an inverse, so the solution set is unchanged.

Subtracting a row from itself has no inverse: it deletes a constraint. For example, replacing $x=1$ by $0=0$ changes a unique solution into an unrestricted variable.

Perform, in order,

$$R_4\leftarrow R_4+R_1,\qquad R_2\leftrightarrow R_3,\qquad R_2\leftarrow -R_2.$$

This yields

$$\left[\begin{array}{rrrrr|r} 1&1&0&0&-1&45\\ 0&1&-1&0&0&10\\ 0&0&1&1&-1&45\\ 0&1&0&1&-1&55 \end{array}\right].$$

Next, $R_4\leftarrow R_4-R_2$ makes row four equal to row three. Now $R_4\leftarrow R_4-R_3$ legitimately produces a zero row:

$$\left[\begin{array}{rrrrr|r} 1&1&0&0&-1&45\\ 0&1&-1&0&0&10\\ 0&0&1&1&-1&45\\ 0&0&0&0&0&0 \end{array}\right].$$

This is row echelon form: the first nonzero entry in each nonzero row is its pivot, pivot positions move right down the rows, and zero rows are at the bottom. Making pivots one and clearing entries above them gives reduced row echelon form.

Pivots, free variables, and the full solution set

Further elimination yields

$$\left[\begin{array}{rrrrr|r} 1&0&0&-1&0&-10\\ 0&1&0&1&-1&55\\ 0&0&1&1&-1&45\\ 0&0&0&0&0&0 \end{array}\right].$$

Columns one through three contain pivots. Set the free variables $s=x_4,t=x_5$:

$$\mathbf x= \begin{pmatrix}s-10\\55-s+t\\45-s+t\\s\\t\end{pmatrix} =\underbrace{\begin{pmatrix}-10\\55\\45\\0\\0\end{pmatrix}}_{\mathbf x_p} +s\underbrace{\begin{pmatrix}1\\-1\\-1\\1\\0\end{pmatrix}}_{\mathbf v_1} +t\underbrace{\begin{pmatrix}0\\1\\1\\0\\1\end{pmatrix}}_{\mathbf v_2}.$$

The particular solution $\mathbf x_p$ solves the equations, but need not satisfy physical nonnegativity. The directions obey $A\mathbf v_1=A\mathbf v_2=\mathbf0$: varying internal flows along either direction leaves the external balances unchanged.

Physical one-way traffic requires every component to be nonnegative:

$$s\ge10,\qquad t\ge0,\qquad s\le45+t.$$

For example, $s=20,t=0$ gives the feasible flow $(10,35,25,20,0)^{\mathsf T}$. The equations describe a translated plane; inequalities select its feasible region.

Rank summarizes the possibilities

Rank is the dimension of the column space and also the number of pivots in echelon form. We use pivot counting here; vector spaces and bases explains its connection to dimension.

For a real system with $m$ equations and $n$ unknowns:

Elimination result	Solutions
A row $0=c$ with $c\ne0$	None
No contradiction and a pivot for every unknown	Exactly one
No contradiction and at least one free variable	Infinitely many

Thus consistency means $\operatorname{rank}(A)=\operatorname{rank}([A\mid\mathbf b])$. A consistent system has $n-\operatorname{rank}(A)$ free variables. Our matrix has rank $3$, leaving two.

Why is one balance redundant? The original coefficient rows satisfy $R_1-R_2+R_3+R_4=0$, and the right-hand sides satisfy $45-45-10+10=0$. Summing junction balances cancels every internal inflow against an internal outflow, leaving the external balance of the entire region. Matrix as Graph expresses this through the incidence matrix.

The general elimination procedure

Suppose the augmented matrix has $m$ rows and $n$ coefficient columns. Let $r$ be the next pivot row, initially one. Process coefficient columns $j=1,\ldots,n$:

1. Search column $j$ in rows $r$ and below for a nonzero entry. If none exists, skip to the next column.
2. If one is found in row $p$, exchange rows $p,r$, obtaining a nonzero pivot $a_{rj}$.
3. For each $i>r$, subtract $a_{ij}/a_{rj}$ times the pivot row from row $i$. Include the right-hand side in every operation.
4. Increase $r$ by one. Stop if no rows remain.

This produces echelon form. For reduced echelon form, work upward from the last pivot, normalize each pivot to one, and clear entries above it. Back substitution alone usually suffices to solve an invertible triangular system; reducing the entire matrix to identity is unnecessary.

An absent pivot in the current column does not mean inconsistency. It means that position supplies no new constraint. A zero coefficient column, for example, leaves its variable unconstrained. Inconsistency requires a contradictory augmented row.

Classifying a parameterized system

Consider

$$\begin{cases} x+y=2,\\ 2x+\lambda y=\mu. \end{cases}$$

Subtract twice the first equation from the second:

$$(\lambda-2)y=\mu-4.$$

For $\lambda\ne2$, the unique solution is

$$y=\frac{\mu-4}{\lambda-2},\qquad x=2-y.$$

For $\lambda=2,\mu=4$, the second equation becomes an identity, giving solutions $(2-t,t)$. For $\lambda=2,\mu\ne4$, it becomes a contradiction.

The cases must be separated before dividing by $\lambda-2$. Dividing immediately would discard every inconsistent or nonunique case.

Why exactly two solutions are impossible

If distinct vectors $\mathbf x_1,\mathbf x_2$ solve the same real linear system, then for every real $t$,

$$A\bigl(\mathbf x_1+t(\mathbf x_2-\mathbf x_1)\bigr) =\mathbf b+t(\mathbf b-\mathbf b)=\mathbf b.$$

Different $t$ give different solutions. A real linear system therefore has zero, one, or infinitely many solutions. General nonlinear equations do not have this restriction.

Measurements must contribute independent information

Measuring $x_5=t$ fixes one parameter but leaves $s$ free. Identifying a general flow by additional linear measurements requires eliminating both free directions.

Measuring $x_4$ and $x_5$ works. Measuring $x_1$ and $x_4$ does not: the original equations already impose $x_4-x_1=10$, so both readings determine only $s$.

More generally, write new measurements as $M\mathbf x=\mathbf d$. Substitution into the parameterization shows that $M\mathbf v_1,M\mathbf v_2$ must be independent to determine both parameters. Counting measurements alone is insufficient. This describes identification by linear equalities for general states; nonnegativity at a particular boundary can further restrict feasibility.

LU saves elimination for new right-hand sides

The traffic matrix is rectangular and rank deficient. To develop ordinary LU for an invertible system, return to the interpolation matrix:

$$V=\begin{pmatrix}1&1&1\\4&2&1\\9&3&1\end{pmatrix},\qquad \mathbf y=\begin{pmatrix}6\\7\\5\end{pmatrix}.$$

Perform

$$R_2\leftarrow R_2-4R_1,\qquad R_3\leftarrow R_3-9R_1,\qquad R_3\leftarrow R_3-3R_2.$$

The resulting upper triangular matrix is

$$U=\begin{pmatrix}1&1&1\\0&-2&-3\\0&0&1\end{pmatrix}.$$

Record the elimination multipliers below the diagonal:

$$L=\begin{pmatrix}1&0&0\\4&1&0\\9&3&1\end{pmatrix}.$$

Then $V=LU$. Check directly: row two of $LU$ is $4U_1+U_2$; row three is $9U_1+3U_2+U_3$, recovering the original rows. In general, a product of elementary elimination matrices gives $EV=U$. In standard elimination without row swaps, the inverse operations form $L=E^{-1}$.

Solve two triangular systems:

$$L\mathbf z=\mathbf y,\qquad U\mathbf c=\mathbf z.$$

Forward substitution gives

$$z_1=6,\qquad z_2=7-4z_1=-17,\qquad z_3=5-9z_1-3z_2=2.$$

Backward substitution gives

$$\gamma=2,\qquad -2\beta-3\gamma=-17,\qquad \alpha+\beta+\gamma=6.$$

Hence $\alpha=-3/2,\beta=11/2,\gamma=2$. These are exactly the required interpolation coefficients [2][2] X. Yang, “ENG1005 Week 3: Interpolation and Fitting, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W3.tex.

For new data $\mathbf y=(1,4,9)^{\mathsf T}$, reuse the same factors. Now $\mathbf z=(1,0,0)^{\mathsf T}$ and the coefficients are $(1,0,0)^{\mathsf T}$, giving $p(t)=t^2$. Factoring a dense square matrix typically costs $O(n^3)$ arithmetic operations; the two triangular solves for each new right-hand side cost $O(n^2)$.

When rows must be exchanged

Invertibility does not make every current pivot nonzero. For example,

$$H=\begin{pmatrix}0&1\\1&1\end{pmatrix}$$

is invertible, but its first entry cannot be used as a divisor. Swap rows, recording the swap in a permutation matrix $P$, to obtain $PH=LU$. Apply the same permutation to the right-hand side:

$$L\mathbf z=P\mathbf b,\qquad U\mathbf x=\mathbf z.$$

Floating-point computation also concerns error amplification by small pivots. Partial pivoting chooses an entry of largest absolute value among the unprocessed rows in the current column. Conditioning and error analysis belong to numerical linear algebra; here the purpose is to understand the factorization.

A complete row-swap example

Solve

$$\begin{pmatrix}0&2\\1&3\end{pmatrix} \begin{pmatrix}x\\y\end{pmatrix} =\begin{pmatrix}4\\7\end{pmatrix}.$$

The current first pivot is zero, so exchange rows:

$$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad PA=\begin{pmatrix}1&3\\0&2\end{pmatrix}.$$

Here $L=I_2$ and $U=PA$. The right-hand side becomes $P\mathbf b=(7,4)^{\mathsf T}$. Back substitution gives $2y=4$ and $x+3y=7$, so $(x,y)=(1,2)$.

Swapping only coefficient rows while retaining the original right-hand side would solve a different system. A permutation records a reordering of complete equations.

General triangular substitution

For a lower triangular $L$ with unit diagonal, forward substitution is

$$z_i=b_i-\sum_{j=1}^{i-1}l_{ij}z_j,\qquad i=1,\ldots,n.$$

Only previously computed values occur on the right. For an upper triangular $U$ with nonzero diagonal entries, backward substitution is

$$x_i=\frac{z_i-\sum_{j=i+1}^n u_{ij}x_j}{u_{ii}},\qquad i=n,n-1,\ldots,1.$$

These formulas assume $A=LU$. For $PA=LU$, replace the first formula’s right-hand side by the corresponding entries of $P\mathbf b$.

Square elimination without swaps requires nonzero pivots at each stage to continue in this form. If the resulting $U$ has nonzero diagonal entries, both triangular systems have unique solutions for every right-hand side. Thus $L,U$, and their product $A$ are invertible.

Exercises

ExerciseUse new measurements

In the traffic model, $x_2=30,x_5=5$. Find all flows and check nonnegativity.

Solution

$t=5$ and $55-s+t=30$ give $s=30$. Thus $\mathbf x=(20,30,20,30,5)^{\mathsf T}$, with all components nonnegative.

ExerciseLocate a contradiction

Change only the first right-hand side of the original traffic system to $46$. Is the system consistent?

Solution

No. The coefficient relation $R_1-R_2+R_3+R_4=0$ still holds, but its right-hand side becomes $46-45-10+10=1$. Elimination produces $0=1$: external flow no longer balances.

ExerciseClassify before dividing

For $x+y=1$ and $2x+ay=b$, give the conditions for a unique solution, no solution, or infinitely many solutions.

Solution

Elimination gives $(a-2)y=b-2$. If $a\ne2$, the unique solution has $y=(b-2)/(a-2),x=1-y$. If $a=2,b=2$, there are infinitely many solutions; if $a=2,b\ne2$, none.

ExerciseReusing triangular factors

Use the chapter’s interpolation factorization $V=LU$ with right-hand side $(2,3,4)^{\mathsf T}$. Find the coefficients.

Solution

Forward substitution gives $\mathbf z=(2,-5,1)^{\mathsf T}$. Back substitution gives $(\alpha,\beta,\gamma)=(0,1,1)$, representing $p(t)=t+1$. Check its values at all three sample points.

References

1. [1] X. Yang, “ENG1005 Week 2: Traffic Flow, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W2.tex ↩
2. [2] X. Yang, “ENG1005 Week 3: Interpolation and Fitting, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W3.tex ↩