Matrices and linear systems

Two totals constrain the same two unknowns

Suppose two identical notebooks and one pen cost 7 units, while one notebook costs 2 units more than one pen. Let x be the notebook price and y the pen price, in the same currency unit. The information becomes 2x+y=7 and x−y=2. A solution must satisfy both equations at once. The pair (3,1) does: 2×3+1=7 and 3−1=2.

Elimination finds that pair without guessing. Swap the order of the equations, then subtract twice x−y=2 from 2x+y=7. This leaves 3y=3, so y=1 and then x=3. We have changed the written equations, but we will justify why their common solutions stay the same.

Preparation: signed-number arithmetic, fractions, one-variable linear equations, and vectors as ordered lists. The preceding Vectors article supplies component arithmetic; its projection and cross-product sections are not required. Read through the solution-classification sections first, then return to matrix multiplication. All matrices here have finitely many real entries and positive row and column counts. Exact fractions in the examples avoid rounding decisions; this is not a lesson on numerical stability.

A matrix records rows and columns in a fixed order

The coefficients of our system form A=[[2,1],[1,−1]]. Double brackets here separate rows: the first row is (2,1), and the second is (1,−1). A matrix with m rows and n columns has shape m×n, read 'm by n'. Its entry aᵢⱼ is in row i, column j. For this A, a₂₁=1 and a₂₂=−1.

For m equations in n unknowns, fix the variable order x₁,…,xₙ. Insert a zero coefficient whenever a variable is absent. Put the right-hand sides in a separate column b. The augmented matrix [A|b] appends this column to A: our example is [[2,1|7],[1,−1|2]]. The vertical bar marks a meaning boundary; the right-hand side is not an extra unknown.

A square matrix has the same number of rows and columns. A rectangular matrix need not. A row is a horizontal list and a column is a vertical list; exchanging their roles generally changes the matrix, although some square matrices are unchanged. Matrix equality requires the same shape and equal corresponding entries.

Add matching entries; scale every entry

Add matrices of the same shape entry by entry: (A+B)ᵢⱼ=aᵢⱼ+bᵢⱼ. Multiply a matrix by a real scalar c by multiplying every entry: (cA)ᵢⱼ=caᵢⱼ. With A=[[2,1],[1,−1]] and B=[[0,3],[−2,4]], A+B=[[2,4],[−1,3]] and 2A=[[4,2],[2,−2]].

These operations inherit the corresponding real-number rules, including A+B=B+A and c(A+B)=cA+cB. The zero matrix of the required shape is the additive identity, and −A is the additive inverse. A 2×3 matrix cannot be added to a 3×2 matrix: matching entry positions require matching shapes. Matrix multiplication will use a different compatibility rule.

Ax combines each row with x, or combines A's columns

Treat x as a column vector with n entries. For A of shape m×n, the product Ax is a column vector with m entries. Its ith entry is aᵢ₁x₁+⋯+aᵢₙxₙ: multiply corresponding entries of row i and x, then add. Thus Ax=b expresses all m equations together.

There is another reading of the same formula. If A's columns are c₁,…,cₙ, then Ax=x₁c₁+⋯+xₙcₙ. Each weight xⱼ scales an entire column. The ith component of this combination is exactly the row sum above, so the two readings agree for every compatible A and x.

Take A=[[2,1,0],[−1,3,2]] and x=(2,−1,3). The two row sums are 4−1+0=3 and −2−3+6=1. The column combination is 2(2,−1)−(1,3)+3(0,2)=(3,1). A accepts three input components and produces two output components. Its number of output components is its number of rows.

Change equations in ways you can undo

There are three elementary row operations: swap two rows; multiply an entire row by a nonzero real number c; or replace Rᵢ by Rᵢ+cRⱼ with i≠j. Apply an operation to every entry in the augmented row, including the right-hand side. Leave the source row Rⱼ unchanged during a row replacement.

Each operation is reversible. Undo a swap with the same swap, scaling by c with scaling by 1/c, and Rᵢ←Rᵢ+cRⱼ with Rᵢ←Rᵢ−cRⱼ. If a vector satisfies the old equations, it satisfies each new linear combination. Conversely, the inverse operation recovers the old equations from the new ones. Thus both systems have exactly the same solution set, including when that set is empty.

Multiplying a row by zero is excluded: x=1 would become 0=0 and lose its constraint. Changing coefficients while leaving the right-hand side fixed is also generally invalid. For example, subtracting twice (1,−1|2) from (2,1|7) gives (0,3|3), not (0,3|7). Column swaps are not row operations; they would change the variable order unless that change were explicitly tracked.

Elimination exposes one unknown at a time

Start with [[2,1|7],[1,−1|2]]. Swap R₁ and R₂ to use a leading 1. Replace R₂ by R₂−2R₁, obtaining [[1,−1|2],[0,3|3]]. The second equation now says 3y=3. Divide R₂ by 3, then replace R₁ by R₁+R₂. The result [[1,0|3],[0,1|1]] reads x=3, y=1.

At every stage, (3,1) satisfies both equations. That check can catch an arithmetic error, but equivalence follows from the reversible-operation argument, not from testing this one pair. Substitute the final answer into the original equations as a separate check.

The intermediate array [[1,−1|2],[0,3|3]] already allows back-substitution: solve the bottom equation, then substitute upward. Clearing above pivots as well produces reduced form, which reads the answer more directly.

Pivots form a staircase, not necessarily a diagonal

In row echelon form (REF), all zero rows are at the bottom; the leading nonzero entry of each nonzero row lies strictly to the right of the leading entry in the row above; and all entries below a leading entry are zero. These leading entries identify pivot positions. Their columns are pivot columns. Leading entries in REF need not equal 1.

Reduced row echelon form (RREF) also requires every leading entry to be 1 and every other entry in its column to be zero. For example, [[1,−1|2],[0,3|3]] is in REF but not RREF. The final [[1,0|3],[0,1|1]] is in both. Entries away from pivot columns need not vanish in RREF.

A practical procedure scans columns from left to right and keeps a current working row. If some entry in that column at or below that row is nonzero, swap it into place, scale it to 1, and clear that column in the other rows. Then advance the working row. If all the candidate entries are zero, skip the column. Stop when all rows or columns have been processed. Each pivot advances the row and column, so the finite procedure terminates.

Do not divide by a zero candidate. In [[0,1,2|5],[0,2,4|10]], skip the first column and use the second. R₂←R₂−2R₁ gives [[0,1,2|5],[0,0,0|0]]. The first variable column is free even though the first pivot is in the first row.

First ask whether any solution exists

A row [0,…,0|d] with d≠0 says 0=d, so there is no solution. Such a system is inconsistent. In echelon form this is a pivot in the augmented column. A zero row [0,…,0|0] instead says 0=0 and contributes no new restriction.

Check for a contradiction before counting variable pivots. The three equations x=2, y=1, 0=1 have pivots in both variable columns, yet no common solution. Reducing their augmented matrix fully can clear the constants in the first two rows; the last row still says 0=1. No amount of other information repairs that contradiction.

For a consistent system, a variable whose column is a pivot column is a pivot variable. Any remaining variable is free. If every variable column has a pivot, there is exactly one solution. Otherwise there are infinitely many real solutions, described by choosing the free variables. The reason for the second conclusion will be made explicit next.

Free variables label every solution, not a few samples

Consider x+y+z=4 and y−z=0. Subtract the second row from the first. RREF is [[1,0,2|4],[0,1,−1|0]], meaning x+2z=4 and y−z=0. The z column has no pivot, so choose z=t for any real t. Then y=t and x=4−2t. Every vector (4−2t,t,t) is a solution, since substitution gives 4−2t+t+t=4 and t−t=0.

Conversely, any solution has some real third component t. The second reduced equation forces its second component to be t, and the first forces its first component to be 4−2t. Hence the formula gives all solutions. Distinct t values give distinct third components, so there are infinitely many; checking only t=0 and t=1 would not prove completeness.

For the empty-first-column example, RREF says y+2z=5 and imposes no equation on x. Put x=s and z=t, where s and t are independent real parameters. The complete solution is (s,5−2t,t). Pivot locations tell us which variables to solve for; neither a missing column entry nor a zero row is a new equation.

The same reasoning works for every consistent RREF system. Each nonzero row has one pivot variable with coefficient 1, zeros in all the other pivot columns, and possibly nonzero coefficients in free columns. Choose any real values for the free variables; each row then determines its own pivot variable uniquely. Zero rows impose no further condition. Conversely, every solution has some such free-variable values and must have those forced pivot values. With no free variables this gives one solution; with at least one, distinct choices change a free coordinate and give infinitely many solutions. Reversible row operations transfer this conclusion to the original system.

Different equation counts can produce the same solution count

For two variables, an equation ax+by=c with (a,b)≠(0,0) is a line. Common solutions lie on every line. The equations x+y=3 and x−y=1 meet at (2,1). The equations x+y=3 and 2x+2y=7 are parallel and distinct, so have no common point; elimination gives 0=1. Replacing 7 by 6 makes the second equation redundant and leaves the entire line (3−t,t).

The degenerate equation 0x+0y=c is not a line: it describes every point when c=0 and no point when c≠0. Algebra handles these cases without trying to draw an ordinary line.

More equations than variables does not guarantee inconsistency or uniqueness. The three equations x=2, y=1, x+y=3 reduce to two variable pivots and a zero row. They have the unique solution (2,1). The zero row expresses redundancy; free variables are counted by missing variable pivots, not by zero rows.

The column reading gives another question: can b be made as a combination of A's columns? That is exactly the existence question for Ax=b. Later lessons study collections of such combinations as vector spaces and introduce bases; the present solution method needs neither concept in advance.

A product composes two compatible input-output rules

Let B have shape n×p and A have shape m×n. A p-component input x first becomes Bx with n components, then A(Bx) with m. Define AB to be the m×p matrix whose jth column is A times the jth column of B. Its entry in row i, column j is (AB)ᵢⱼ=Σₖ₌₁ⁿ aᵢₖbₖⱼ: row i of A paired with column j of B. The symbol Σ means add the indicated terms: here aᵢ₁b₁ⱼ+⋯+aᵢₙbₙⱼ, with k running from 1 to n.

Expanding finite sums proves (AB)x=A(Bx). The ith entry on either side is ΣⱼΣₖ aᵢₖbₖⱼxⱼ; regrouping finite sums is valid. Thus, with column-vector inputs, AB applies B first and A second. Matching inner dimensions are required; the output shape uses the outer dimensions.

For A=[[2,1,0],[−1,3,2]] of shape 2×3 and B=[[1,0],[0,1],[1,−1]] of shape 3×2, AB=[[2,1],[1,1]] has shape 2×2. Its bottom-left entry is (−1)×1+3×0+2×1=1. BA is also defined in this particular example, but has shape 3×3. In other shape combinations one order may be defined while the reverse is not.

Rotate then shear gives a different result from shear then rotate

In ordinary oriented plane coordinates, let R=[[0,−1],[1,0]] rotate a column vector a quarter-turn anticlockwise, and let S=[[1,1],[0,1]] shear it horizontally. Their rules are R(x,y)=(−y,x) and S(x,y)=(x+y,y). The definitions specify the actions; the diagram displays their consequences.

For u=(1,2), R acts first in SRu: u→(−2,1)→(−1,1). For RSu, S acts first: u→(3,2)→(−2,3). Direct multiplication gives SR=[[1,−1],[1,0]] and RS=[[0,−1],[1,1]], which are different matrices. Therefore AB=BA is not a general matrix rule, even for square matrices of the same shape.

The order of the letters is read from the input outward. This is the same function-composition order as A(Bx). Comparing both paths from the same input isolates the effect of order. Some particular matrices commute, but a single pair that fails is enough to disprove a universal commutative law.

Keep the valid algebraic rules and question the others

The identity matrix Iₙ has 1 on its diagonal and 0 elsewhere. It leaves every n-component column unchanged. For A of shape m×n, IₘA=A and AIₙ=A. Compatible matrix products are associative and distribute over addition. Associativity follows by expanding and regrouping finite entry sums, just as in the proof of (AB)x=A(Bx).

Cancellation requires extra conditions. With D=[[1,0],[0,0]] and E=[[0,0],[0,1]], both matrices are nonzero but DE is the zero matrix. Thus a zero product need not have a zero factor. Also DI₂=DD although I₂≠D, so a common nonzero left factor cannot always be cancelled. The inverse-matrix lesson will explain when cancellation is justified; nonzero alone is insufficient.

Return to the original equations and their meaning

A reliable solution records the variable order, shapes, operations and any free parameters. Check for contradictions first, express pivot variables in terms of free variables when the system is consistent, and substitute the resulting vector or parameter formula into the original equations. The notebook example gives positive prices in the stated unit, so its mathematical answer also meets its original interpretation.

A real solution of an equation need not satisfy an application's additional constraints. Counts may have to be whole and nonnegative; lengths may need to be positive. State those restrictions separately and filter the real solution set accordingly. A nonempty real solution set does not guarantee a physically admissible answer.

Exact elimination explains solution structure here. With measured data or floating-point arithmetic, a very small computed entry cannot automatically be treated as an exact zero. Rounding, conditioning and numerical methods need their own analysis. Continue next to vector spaces and combinations; return later for determinants, inverses and least squares.

Worked examples

Try it yourself

1. For A=[[2,1,0],[−1,3,2]], state its shape and a₂₃.

   Show the answer and reasoning

   2×3 and a₂₃=2.

   Count rows before columns; entry a₂₃ is in row 2, column 3.

2. Find [[1,2],[0,−1]]+[[3,0],[2,4]].

   Show the answer and reasoning

   [[4,2],[2,3]].

   The shapes agree, so add corresponding entries.

3. Find [[1,2],[3,0]](2,−1).

   Show the answer and reasoning

   (0,6).

   The row sums are 1×2+2×(−1)=0 and 3×2+0×(−1)=6.

4. Apply R₂←R₂−2R₁ to [[1,−1|2],[2,1|7]].

   Show the answer and reasoning

   [[1,−1|2],[0,3|3]].

   The right-hand side changes with the coefficients: 7−2×2=3.

5. Why may you not replace an equation by zero times itself when preserving solutions?

   Show the answer and reasoning

   It can discard a constraint.

   For example, x=1 becomes 0=0; the operation cannot be undone and admits extra solutions.

6. Is [[1,−1|2],[0,3|3]] in REF? Is it in RREF?

   Show the answer and reasoning

   REF: yes. RREF: no.

   Leading entries move right with zeros below. The second pivot is not 1, and its column also has −1 above it.

7. What does [[1,0|2],[0,1|1],[0,0|1]] say about the number of solutions?

   Show the answer and reasoning

   No solution.

   The last row says 0=1. Pivots in all variable columns do not override inconsistency.

8. How many solutions does [[1,0|2],[0,1|1],[0,0|0]] have?

   Show the answer and reasoning

   Exactly one: (2,1).

   The system is consistent and each variable column has a pivot. A zero row does not by itself create a free variable.

9. Give every solution represented by [[1,0,2|4],[0,1,−1|0]].

   Show the answer and reasoning

   (4−2t,t,t), t∈R.

   Column 3 is free; putting z=t forces y=t and x=4−2t. Conversely these values satisfy both equations for every real t.

10. In [[0,1,2|5],[0,0,0|0]], with variable order x,y,z, which variables are free?

    Show the answer and reasoning

    x and z; solutions are (s,5−2t,t), s,t∈R.

    Only column 2 has a variable pivot. The augmented column is not a variable column.

11. If A has shape 2×3 and B has shape 3×4, give the shape of AB and decide whether BA is defined.

    Show the answer and reasoning

    AB has shape 2×4; BA is undefined.

    The inner dimensions 3 match for AB. For BA, 4 and 2 do not match.

12. Which action comes first in SRu with column-vector inputs? For u=(1,2), what is SRu?

    Show the answer and reasoning

    R comes first; SRu=(−1,1).

    Compute R(1,2)=(−2,1), then S(−2,1)=(−1,1).

13. Can two nonzero 2×2 matrices have a zero product? Give an example.

    Show the answer and reasoning

    Yes: D=[[1,0],[0,0]] and E=[[0,0],[0,1]] give DE=0.

    Each row-column sum vanishes even though each factor has a nonzero entry. Scalar zero-product and cancellation rules do not transfer without conditions.

What to carry forward

• Shape and variable order are part of a matrix calculation; the augmented column records totals, not another variable.
• Ax can be read as row products or as a combination of columns, with matching input dimension.
• Reversible operations on entire augmented rows preserve exactly the solution set.
• Echelon pivots form a staircase; skip empty candidate columns and never divide by zero.
• Check consistency first, then count free variable columns to distinguish unique from infinite real solutions.
• A complete parameterization proves both that every parameter choice works and that every solution is included.
• For column inputs, AB applies B first; compatible dimensions do not make multiplication commutative.
• Exact algebraic solutions still need the original problem's units and admissibility conditions.