What are the possible outcomes of a linear system?

A linear system has exactly one of three outcomes: no solution (inconsistent, contradictory equations), exactly one solution (full column rank, no free variables), or infinitely many solutions (consistent with free variables). A system can never have exactly two or any other finite number greater than one.

What is the augmented matrix?

The augmented matrix [A | b] combines the coefficient matrix A and right-hand side b into a single m×(n+1) matrix. Row operations on the augmented matrix correspond to legal algebraic manipulations of the equations. Comparing the rank of A to the rank of [A | b] determines whether the system is consistent.

When does a linear system have a solution?

A solution exists if and only if rank(A) = rank([A | b]), meaning b lies in the column space of A. If a solution exists, it is unique when rank(A) = n (no free variables). When A is square and invertible, a unique solution exists for every b.

What is a homogeneous linear system?

A homogeneous system Ax = 0 always has the trivial solution x = 0. Nontrivial solutions exist if and only if rank(A) < n. The solution set is the null space of A — a subspace of Rⁿ with dimension n − rank(A). If there are more unknowns than equations, nontrivial solutions are guaranteed.

What are the three elementary row operations?

The three operations are: swapping two rows, multiplying a row by a nonzero scalar, and adding a multiple of one row to another. Each is reversible, so none changes the solution set. They reduce the augmented matrix to echelon form, from which the solution is read by back substitution.

Systems of Linear Equations

Q: What are the three elementary row operations?

The three operations are: swapping two rows, multiplying a row by a nonzero scalar, and adding a multiple of one row to another. Each is reversible, so none changes the solution set. They reduce the augmented matrix to echelon form, from which the solution is read by back substitution.

What a Linear System Is

Writing a System in Matrix Form

The Augmented Matrix

The Three Possible Outcomes

Geometric Interpretation

Elementary Row Operations

Row Echelon Form and Reduced Row Echelon Form

Homogeneous Systems

When Does a Solution Exist? When Is It Unique?

Solution Methods Beyond Row Reduction

Summary: Rank Conditions and Solution Sets

Solving Ax = b

A linear system is a collection of linear equations in several unknowns. Writing it in matrix form as Ax = b transforms the problem into a question about matrices: is b in the column space of A, and if so, what are the weights? Row reduction answers both questions systematically, and the rank of the coefficient matrix determines whether the solution exists, whether it is unique, and what the solution set looks like.

What a Linear System Is

A linear system is a set of

m

equations in

n

unknowns where each equation is a linear combination of the unknowns equal to a constant:

a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1

a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2

\vdots

a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m

"Linear" means no products of unknowns, no powers higher than

1

, and no transcendental functions of unknowns. The expression

3x_1 - 2x_2 + x_3 = 7

is linear; the expression

x_1 x_2 + x_3^2 = 1

is not.

A solution is an assignment of values to

x_1, \dots, x_n

that satisfies every equation simultaneously. The solution set is the collection of all solutions. The central question is: what does this set look like?

Writing a System in Matrix Form

The entire system can be compressed into a single matrix equation:

A\mathbf{x} = \mathbf{b}

where

A

is the

m \times n

coefficient matrix with entry

a_{ij}

in row

i

, column

j

;

\mathbf{x} = (x_1, x_2, \dots, x_n)^T

is the unknown vector; and

\mathbf{b} = (b_1, b_2, \dots, b_m)^T

is the right-hand side.

Each row of

A

corresponds to one equation. Each column corresponds to one unknown. The matrix-vector product

A\mathbf{x}

is a linear combination of the columns of

A

weighted by the entries of

\mathbf{x}

A\mathbf{x} = x_1 \mathbf{a}_1 + x_2 \mathbf{a}_2 + \cdots + x_n \mathbf{a}_n

Asking whether

A\mathbf{x} = \mathbf{b}

has a solution is therefore equivalent to asking whether

\mathbf{b}

lies in the column space of

A

— whether

\mathbf{b}

can be assembled from the columns using some choice of weights.

The Augmented Matrix

The augmented matrix packages the coefficient matrix and the right-hand side into a single object:

[A \mid \mathbf{b}] = \left(\begin{array}{cccc|c} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{array}\right)

The vertical bar separates the coefficients from the constants but is purely notational — the augmented matrix is an

m \times (n+1)

matrix on which row operations are performed. Every row operation on

[A \mid \mathbf{b}]

corresponds to a legal algebraic manipulation of the equations: swapping two equations, multiplying an equation by a nonzero scalar, or adding a multiple of one equation to another. None of these changes the solution set.

The augmented matrix is the object that Gaussian elimination operates on, and comparing its rank to the rank of

A

alone determines whether the system is consistent.

The Three Possible Outcomes

A linear system

A\mathbf{x} = \mathbf{b}

has exactly one of three outcomes.

No solution: the system is inconsistent. The equations impose contradictory constraints — there is no

\mathbf{x}

that satisfies all of them. In the augmented matrix, this manifests as a row of the form

[0 \; 0 \; \cdots \; 0 \mid d]

with

d \neq 0

, representing the impossible equation

0 = d

.

Exactly one solution: the system is consistent and determined. There is a unique

\mathbf{x}

satisfying all equations. This requires the coefficient matrix to have rank equal to

n

(the number of unknowns), leaving no free variables.

Infinitely many solutions: the system is consistent but underdetermined. The constraints do not pin down a single point — the solution set is a line, plane, or higher-dimensional flat parametrized by free variables.

There is no fourth option. A linear system never has exactly two solutions, or ten, or any finite number greater than one. The proof is simple: if

\mathbf{x}_1

and

\mathbf{x}_2

are both solutions with

\mathbf{x}_1 \neq \mathbf{x}_2

, then

\mathbf{x}_1 + t(\mathbf{x}_2 - \mathbf{x}_1)

is a solution for every

t \in \mathbb{R}

, producing infinitely many.

Outcome	How it appears in the reduced augmented matrix	Rank condition
No solution (inconsistent)	a row of the form [0 0 ⋯ 0 \| d] with d ≠ 0 — the impossible equation 0 = d	rank(A) < rank([A \| b])
Exactly one solution	every column of A has a pivot; no free variables; every x_i is determined	rank(A) = rank([A \| b]) = n
Infinitely many solutions	at least one column of A has no pivot; the corresponding variable is free	rank(A) = rank([A \| b]) < n

Geometric Interpretation

Each equation in a linear system defines a hyperplane in

\mathbb{R}^n

. The solution set is the intersection of all

m

hyperplanes.

For two equations in two unknowns, each equation is a line in

\mathbb{R}^2

. Two distinct non-parallel lines meet at exactly one point — a unique solution. Parallel lines never meet — no solution. Coincident lines (the same line described twice) overlap entirely — infinitely many solutions.

For three equations in three unknowns, each equation is a plane in

\mathbb{R}^3

. Three planes can intersect in a point, along a line, or not at all. They can also coincide or be arranged so that each pair intersects but no point lies on all three — a triangular prism configuration that yields no solution.

In higher dimensions the geometry is harder to visualize but the classification persists. The rank of the coefficient matrix counts how many hyperplanes cut independently — each independent equation reduces the dimension of the intersection by one. If the rank is

r

and the system is consistent, the solution set has dimension

n - r

Elementary Row Operations

The three elementary row operations are the legal moves that transform one augmented matrix into another without altering the solution set.

Swapping two rows (

R_i \leftrightarrow R_j

) reorders the equations. Multiplying a row by a nonzero scalar (

kR_i \to R_i

) rescales an equation. Adding a multiple of one row to another (

R_i + cR_j \to R_i

) replaces one equation with a combination of two equations.

Each operation is reversible: a swap undoes itself, scaling by

k

is reversed by scaling by

1/k

, and adding

c

times row

j

to row

i

is reversed by subtracting

c

times row

j

from row

i

. Reversibility guarantees that the solution set is unchanged — no solutions are created or destroyed.

Each row operation corresponds to left-multiplication by an elementary matrix. This algebraic interpretation connects the row-reduction algorithm to the theory of matrix factorization and invertibility. The full systematic application of row operations is Gaussian elimination.

Row Echelon Form and Reduced Row Echelon Form

Row operations aim to reduce the augmented matrix to a standard shape from which the solution can be read.

Row echelon form (REF) has a staircase pattern: the leading entry of each row is to the right of the leading entry of the row above, and all entries below each leading entry are zero. In REF, the solution is obtained by back substitution — solving from the bottom row upward.

Reduced row echelon form (RREF) goes further: each leading entry is

1

and is the only nonzero entry in its column. In RREF, the solution is visible by inspection — each pivot variable is already isolated.

The RREF of any matrix is unique. Different sequences of row operations always arrive at the same RREF. This uniqueness makes the pivot positions intrinsic to the matrix: the rank, the free variables, and the solvability verdict all follow from the pivot structure. The full treatment of both forms, including how to read solutions from each, is on the echelon form page.

Homogeneous Systems

The special case

A\mathbf{x} = \mathbf{0}

— where every right-hand side entry is zero — is called a homogeneous system. It is always consistent, since

\mathbf{x} = \mathbf{0}

satisfies every equation. The question is whether nontrivial solutions exist.

Nontrivial solutions exist if and only if the rank of

A

is less than

n

. If the system has more unknowns than equations (

n > m

), nontrivial solutions are guaranteed — the rank cannot exceed

m

, which is less than

n

.

The solution set of a homogeneous system is the null space of

A

: a subspace of

\mathbb{R}^n

with dimension

n - \text{rank}(A)

. The superposition principle holds — any linear combination of solutions is again a solution — which is why the solution set has the clean structure of a vector space rather than an arbitrary collection of points.

When Does a Solution Exist? When Is It Unique?

The rank of

A

determines both existence and uniqueness of solutions to

A\mathbf{x} = \mathbf{b}

.

Existence: a solution exists if and only if

\text{rank}(A) = \text{rank}([A \mid \mathbf{b}])

. This means

\mathbf{b}

lies in the column space of

A

— appending it as an extra column does not introduce a new independent direction.

Uniqueness: if a solution exists, it is unique if and only if

\text{rank}(A) = n

. Full column rank means no free variables and a trivial null space, so the particular solution stands alone with no homogeneous component to add freedom.

When

A

is square (

m = n

) and

\det(A) \neq 0

, both conditions hold for every

\mathbf{b}

: the system always has a unique solution, given by

\mathbf{x} = A^{-1}\mathbf{b}

. When

A

is rectangular or singular, the analysis requires comparing ranks and identifying free variables. The full treatment, including overdetermined and underdetermined systems, is on the solvability page.

Solution Methods Beyond Row Reduction

Gaussian elimination is the most general and widely used method, but several alternatives exist for special cases.

Cramer's rule solves an

n \times n

system by expressing each unknown as a ratio of determinants. It gives a closed-form solution but is computationally impractical for large

n

.

The inverse formula

\mathbf{x} = A^{-1}\mathbf{b}

applies when

A

is square and invertible. It is elegant but rarely the most efficient approach — computing

A^{-1}

costs roughly three times as much as solving by elimination.

LU decomposition factors

A

into a lower triangular matrix

L

and an upper triangular matrix

U

. Once the factorization is computed, solving

A\mathbf{x} = \mathbf{b}

reduces to two cheap triangular solves. This is the method of choice when multiple systems share the same coefficient matrix

A

but have different right-hand sides.

Iterative methods — Jacobi, Gauss-Seidel, conjugate gradient — generate a sequence of approximations converging to the solution. They are preferred for very large sparse systems where direct methods would require too much memory or time. These methods lie at the boundary between linear algebra and numerical analysis.

Method	When it applies	Cost / notes
Gaussian elimination	any system; the most general method	≈ (2/3)n³ operations; the default workhorse
Cramer's rule	square n × n with det(A) ≠ 0; small n or symbolic work	n + 1 determinant evaluations; impractical for large n
Inverse formula x = A⁻¹b	square A with det(A) ≠ 0	computing A⁻¹ costs roughly 3× elimination; rarely the most efficient choice
LU decomposition	multiple right-hand sides b sharing the same coefficient matrix A	one factorization (cost of elimination) plus cheap triangular solves for each b
Iterative methods (Jacobi, Gauss-Seidel, CG)	very large sparse systems where direct methods are too costly	produces a sequence of approximations; convergence depends on the matrix structure

Summary: Rank Conditions and Solution Sets

The rank of A and its relationship to the rank of the augmented matrix [A | b] settles every question about A·x = b — whether a solution exists, whether it is unique, and what shape the solution set takes. The table below collects each rank pattern alongside the resulting outcome, the structure of the solution set, and the geometric picture, providing a single reference card for the hub.

Rank pattern	Outcome	Solution set structure	Geometric picture
rank(A) < rank([A \| b])	inconsistent	empty	hyperplanes with no common point (e.g., parallel lines in ℝ²)
rank(A) = rank([A \| b]) = n	consistent and determined	a single point in ℝⁿ	n independent hyperplanes meet at one point
rank(A) = rank([A \| b]) = r < n	consistent and underdetermined	affine flat: particular solution + null space of A; dimension n − r	hyperplanes intersect along a line, plane, or higher flat
rank(A) < n with b = 0 (homogeneous)	nontrivial solutions exist	null space of A; subspace of dimension n − rank(A)	a subspace through the origin