Skip to content
LumenaryAcademy
Practice 60 min

Linear algebra and linear systems

Solving systems with backslash and what it does underneath, conditioning, least squares, eigenvalues and sparse matrices.

Code tested · 5AI-draftedAwaiting review by a computer scientist
MotivationH

Where MATLAB began

Behind a surprising share of science and engineering sits one problem: find the vector xx with Ax=bAx = b. The forces in a bridge, the currents in a circuit, the temperatures inside an engine block, the prices that balance a market model and the coefficients of a curve fitted to data all come down to a matrix, a known right-hand side and an unknown vector. Large simulations solve such systems millions of times.

MATLAB was born to make this easy. Cleve Moler wrote the first version so that students could call the LINPACK and EISPACK libraries without writing Fortran (lesson 1 tells the story), and solving a linear system is still a single character, the backslash. This lesson shows how to use it, what it does behind the scenes, and, just as important, when to distrust its answer. Then it turns to the other workhorses of numerical linear algebra: least squares for fitting models to data, eigenvalues for understanding how systems evolve, and sparse matrices for problems with millions of unknowns.

You need only the matrix product from lesson 3 and some memory of solving two equations in two unknowns at school. The mathematics is explained as it comes; for a full course on it, see the references.

DefinitionsH

Backslash, slash and the residual

Definition— Backslash (left division)

x = A \ b solves the system Ax=bAx = b. Read it as "A divides b from the left": in ordinary algebra you would write x=A−1bx = A^{-1}b, but MATLAB never forms the inverse. If A is square and nonsingular, the solution is unique. If A has more rows than columns, backslash returns the least-squares solution, the x that makes A*x as close to b as possible. If b has several columns, it solves for each column at once. The function form is mldivide(A, b).

Definition— Slash (right division)

y = c / A solves yA=cyA = c, where y and c are rows. It is the same problem transposed: c / A equals (A' \ c')'. Most code uses backslash; slash appears when data are naturally rows.

Definition— Residual

The residual of a computed solution x is A*x - b. Its size, measured with norm (the length of a vector), says how well x satisfies the equations. As you will see, a tiny residual does not always mean an accurate x.

Definition— Condition number

cond(A) measures how much the solution of Ax=bAx = b can change when A or b changes slightly. A condition number near 1 is ideal; as a rule of thumb, a condition number of 10k10^k can cost you about kk of the roughly 16 significant digits a double carries. A singular matrix (no unique solution) has an infinite condition number.

Worked examplesH

Solving a system

Three shoppers at a market in Kumasi each bought mangoes, bananas and oranges, in different amounts, and remember only what they paid in total. What did each fruit cost per kilogram? Each basket gives one equation, so three baskets give a 3-by-3 system:

matlab
% Three shoppers at a market: kilograms of mangoes, bananas and oranges
% in each basket (one row per shopper), and what each paid.
A = [2 1 3
     1 2 1
     3 1 2];
b = [17; 9; 16];

x = A \ b;
fprintf('price per kg: mangoes %.2f, bananas %.2f, oranges %.2f\n', x);
fprintf('residual norm(A*x - b) = %.1e\n', norm(A * x - b));
fprintf('det(A) = %g, rank(A) = %d, cond(A) = %.2f\n', det(A), rank(A), cond(A));

% Two weeks of bills at once: one column per week.
B = [17 17.8
      9  9.2
     16 17.0];
X = A \ B

% The row form: solve y*A = c with the forward slash.
y = b' / A';
fprintf('slash agrees with backslash: %d\n', norm(y' - x) < 1e-12);

% What backslash did: an LU factorisation with row pivoting.
[L, U, P] = lu(A)
fprintf('norm(P*A - L*U) = %.1e\n', norm(P * A - L * U));

% Reuse the factors for a third week, with two triangular solves.
b3 = [18.1; 9.6; 17.1];
x3 = U \ (L \ (P * b3));
fprintf('week 3: %.2f %.2f %.2f\n', x3);
text
price per kg: mangoes 2.50, bananas 1.50, oranges 3.50
residual norm(A*x - b) = 0.0e+00
det(A) = -8, rank(A) = 3, cond(A) = 5.56
X =

   2.5000   2.8000
   1.5000   1.4000
   3.5000   3.6000

slash agrees with backslash: 1
L =

   1.0000        0        0
   0.3333   1.0000        0
   0.6667   0.2000   1.0000

U =

   3.0000   1.0000   2.0000
        0   1.6667   0.3333
        0        0   1.6000

P =

Permutation Matrix

   0   0   1
   0   1   0
   1   0   0

norm(P*A - L*U) = 0.0e+00
week 3: 2.70 1.60 3.70
  • Always check the residual of a solution you care about. Here it is zero; in general expect something near eps times the size of the numbers involved.
  • rank(A) is 3, so the three baskets really are independent equations, and cond(A) is small, so the prices are trustworthy. (If two shoppers had bought the same mixture, the rank would drop and no amount of arithmetic could separate the prices.)
  • Many right-hand sides go in the columns of one matrix: A \ B solves for both weeks in one call, sharing all the expensive work.
  • lu shows that work. Backslash rewrote A as a product of a lower-triangular L and an upper-triangular U, after reordering rows (the permutation P) to divide by the largest available numbers, which keeps rounding errors small. This is Gaussian elimination, recorded. Once you have the factors, a new right-hand side costs only two triangular solves, which are very cheap; backslash recognises triangular matrices and solves them directly by substitution.
  • Octave displays P as a special "Permutation Matrix" (just as it displays eye(3) as a "Diagonal Matrix"); MATLAB shows an ordinary matrix. Both behave identically in arithmetic.
ExplanationH

What backslash does, and why not inv

Backslash is not one algorithm but a dispatcher. Both MATLAB and Octave look at the matrix before choosing how to solve:

The matrix is…Backslash uses…
triangular (or a permuted triangle)forward or back substitution
symmetric with a positive diagonalfirst tries a Cholesky factorisation, A=RTRA = R^\mathsf{T}R, about twice as fast as LU, and falls back to a general method if that fails
square, otherwiseLU with partial pivoting
rectangularQR factorisation, giving the least-squares solution
sparsespecialised sparse solvers (from the SuiteSparse library, in both programs)

The dense factorisations themselves come from LAPACK, the successor to LINPACK, running on an optimised BLAS, so MATLAB and Octave solve dense systems at comparable speed.

You will often see inv(A) * b in code written by people who learned linear algebra on paper. Avoid it. Computing the inverse costs about three times as much as an LU factorisation, multiplying by it is less accurate, and for sparse matrices it is a disaster, because the inverse of a sparse matrix is usually completely full. If you need to solve with the same matrix many times, keep the factors (as above) rather than the inverse. MATLAB also offers a decomposition object that stores the right factorisation for reuse; Octave 11 does not have it, so the portable way is lu or chol. And det(A) is a poor test for singularity: scaling a 100-by-100 matrix by 0.1 multiplies its determinant by 10−10010^{-100} without making it any harder to solve. Use rcond or cond instead, as the next example does.

Worked examplesH

When to distrust the answer

The Hilbert matrix, whose element (i, j) is 1/(i + j − 1), is a famous example of a matrix that is perfectly nonsingular in exact arithmetic and terribly conditioned in floating point. hilb(n) builds it. The program below chooses the answer in advance (a vector of ones), builds the right-hand side from it, solves, and compares:

matlab
% Solve H*x = b where the exact answer is known to be all ones.
fprintf('%3s %12s %12s %12s\n', 'n', 'cond(H)', 'rel. error', 'residual');
for n = [4 7 10 11]
  H = hilb(n);
  xTrue = ones(n, 1);
  b = H * xTrue;
  x = H \ b;
  fprintf('%3d %12.2e %12.2e %12.2e\n', n, cond(H), norm(x - xTrue) / norm(xTrue), norm(H * x - b) / norm(b));
end

% Two tiny systems: nearly singular and exactly singular.
N = [1 1; 1 1.000001];
S = [1 2; 2 4];
fprintf('rcond: nearly singular %.1e, singular %.1e, well conditioned %.1e\n', ...
        rcond(N), rcond(S), rcond([2 1; 1 3]));
fprintf('rank(S) = %d, null(S) direction = [%.4f %.4f]\n', rank(S), abs(null(S)));
text
  n      cond(H)   rel. error     residual
  4     1.55e+04     2.67e-13     4.06e-17
  7     4.75e+08     9.61e-09     6.47e-17
 10     1.60e+13     1.73e-04     8.82e-17
 11     5.23e+14     3.25e-03     1.12e-16
rcond: nearly singular 2.5e-07, singular 0.0e+00, well conditioned 3.1e-01
rank(S) = 1, null(S) direction = [0.8944 0.4472]

Read the table row by row. The residual stays at rounding level in every case: backslash always finds an x that satisfies the equations to machine precision. But the error in x grows with the condition number, just as the rule of thumb predicts: with cond around 101310^{13}, only three or four of the sixteen digits are right. This is not a bug in the solver. The problem itself is so sensitive that rounding the entries of H to doubles already changed the true answer by that much.

rcond estimates the reciprocal of the condition number cheaply, so values near 0 are a warning sign and values near 1 are healthy. For S, whose second row is twice the first, rank is 1 and null(S) gives the direction in which S maps vectors to zero: any multiple of (2, −1), normalised, can be added to a solution without changing S*x. (The abs keeps the printout independent of the sign each program happens to choose.)

Ask backslash to solve a singular or nearly singular system and both programs still return numbers (not necessarily the same numbers), with a warning: Octave prints warning: matrix singular to machine precision, and MATLAB warns that the matrix is close to singular or badly scaled. Never ignore that warning; the numbers that come with it are usually meaningless. In a program, check rcond yourself and raise an error with a clear message, as in lesson 4.

Worked examplesH

Least squares: fitting a model to data

With more equations than unknowns there is usually no exact solution, and backslash returns the xx that minimises the length of the residual, ∥Ax−b∥\lVert Ax - b \rVert. That is exactly what fitting a model to noisy data means.

A driving instructor measures stopping distances at nine speeds. Physics suggests a model: during the driver's reaction time tt the car travels tvtv, and braking with deceleration aa adds v2/(2a)v^2/(2a). The model is linear in the unknowns tt and 1/(2a)1/(2a), so it becomes a 9-by-2 system:

matlab
% Stopping distances measured in a (made-up) driving test, at nine speeds.
kmh = (20:10:100)';
d = [11.1 16.6 26.7 34.2 43.3 57.0 70.5 80.9 97.3]';
v = kmh / 3.6;                       % speed in metres per second

% Model: d = t*v + v^2/(2*a), reaction time t and braking deceleration a.
M = [v, v.^2];                       % 9 equations, 2 unknowns
c = M \ d;                           % least-squares solution
fprintf('reaction time %.2f s, deceleration %.2f m/s^2\n', c(1), 1 / (2 * c(2)));

r = d - M * c;
fprintf('residual norm %.3f m, largest miss %.2f m\n', norm(r), max(abs(r)));
fprintf('R^2 = %.4f\n', 1 - sum(r.^2) / sum((d - mean(d)).^2));

% The normal equations give the same answer here, less safely in general.
cNormal = (M' * M) \ (M' * d);
fprintf('difference from normal equations: %.1e\n', norm(c - cNormal));
fprintf('cond(M) = %.0f, cond(M''*M) = %.0f\n', cond(M), cond(M' * M));

% polyfit fits a full quadratic, intercept included.
p = polyfit(v, d, 2);
fprintf('polyfit: %.4f v^2 + %.4f v + %.4f\n', p);
fprintf('predicted stopping distance at 120 km/h: %.1f m\n', [120/3.6, (120/3.6)^2] * c);
text
reaction time 1.50 s, deceleration 6.95 m/s^2
residual norm 3.318 m, largest miss 1.74 m
R^2 = 0.9985
difference from normal equations: 8.7e-15
cond(M) = 92, cond(M'*M) = 8526
polyfit: 0.0735 v^2 + 1.4401 v + 0.4376
predicted stopping distance at 120 km/h: 129.8 m
  • The design matrix M has one column per unknown coefficient, each column being that coefficient's term evaluated at every data point. Any model that is a linear combination of known functions (polynomials, sines and cosines, exponentials with fixed rates) is fitted this way, however curved the functions are.
  • The fitted coefficients have physical meaning: a reaction time of 1.5 s and a deceleration of about 7 m/s², typical of a car braking hard on dry asphalt. That interpretability is the reward for choosing a model from the physics rather than fitting an arbitrary curve.
  • R2R^2 is the fraction of the variation in d that the model explains; 0.9985 is excellent.
  • Textbooks derive least squares through the normal equations MTMc=MTdM^\mathsf{T}Mc = M^\mathsf{T}d. They give the same answer here, but M'*M has the square of M's condition number, so on harder problems they lose twice as many digits. Backslash uses a QR factorisation of M instead and never forms M'*M.
  • polyfit(x, y, n) fits a degree-n polynomial (it also uses QR) and returns coefficients from the highest power down, ready for polyval. Its quadratic includes a constant term, which our physical model deliberately leaves out: at speed zero, the stopping distance is zero.
  • Inside the format text, '' is how you write a single quote in a single-quoted char array.

Prediction at 120 km/h is an extrapolation, beyond the measured speeds. The physics makes it more trustworthy than a blind polynomial would be, but it is still a guess outside the data.

Worked examplesH

Eigenvalues: where a system settles

An eigenvector of a square matrix AA is a nonzero vector vv that AA only stretches: Av=λvAv = \lambda v, where the number λ\lambda is its eigenvalue. Eigenvalues describe how a system evolves when the same matrix is applied again and again: components along eigenvectors with ∣λ∣<1|\lambda| \lt 1 die away, and those with λ=1\lambda = 1 stay. eig(A) returns the eigenvalues; [V, D] = eig(A) returns eigenvectors as the columns of V and the eigenvalues on the diagonal of D, so that A*V = V*D.

A city's bike-share scheme has three docks. From records, the operator knows what fraction of the bikes at each dock end the day at each dock. Where will the bikes be in the long run?

matlab
% A bike-share scheme with three docks. P(i, j) is the probability that a
% bike starting the day at dock i ends it at dock j; each row sums to 1.
docks = {'Market', 'University', 'Harbour'};
P = [0.80 0.15 0.05
     0.10 0.70 0.20
     0.10 0.30 0.60];

% Day by day: where 300 bikes, all starting at the market, end up.
bikes = [300 0 0];
for day = 1:30
  bikes = bikes * P;
  if any(day == [1 2 7 30])
    fprintf('day %2d: %6.1f %6.1f %6.1f\n', day, bikes);
  end
end

% The long-run share is a left eigenvector of P for the eigenvalue 1:
% share * P = share, or equivalently P' * share' = share'.
[V, D] = eig(P');
lambda = diag(D);
fprintf('eigenvalues: %s\n', mat2str(sort(lambda, 'descend')', 4));
[~, k] = min(abs(lambda - 1));
share = V(:, k) / sum(V(:, k));
for i = 1:numel(docks)
  fprintf('%-10s %5.1f%%  (%5.1f bikes)\n', docks{i}, 100 * share(i), 300 * share(i));
end
text
day  1:  240.0   45.0   15.0
day  2:  198.0   72.0   30.0
day  7:  116.5  116.7   66.8
day 30:  100.0  125.0   75.0
eigenvalues: [1 0.7 0.4]
Market      33.3%  (100.0 bikes)
University  41.7%  (125.0 bikes)
Harbour     25.0%  ( 75.0 bikes)

This is a Markov chain: the state tomorrow is the state today times a matrix of transition probabilities. Simulating day by day, the bikes drift from the market to a steady split of 100, 125 and 75. The eigenvector for eigenvalue 1 gives that split directly, without simulating. Eigenvectors are only defined up to a scale factor (and MATLAB and Octave may return them with different signs), so dividing by the sum turns it into shares that add up to 1. The second eigenvalue, 0.7, tells you how fast the system settles: the distance from equilibrium shrinks by a factor of about 0.7 a day, so after 30 days it is 0.730≈2×10−50.7^{30} \approx 2 \times 10^{-5} of what it was, which is why day 30 already matches the eigenvector. The same mathematics, at an enormous scale, was behind Google's original PageRank.

Two relatives of eig are worth knowing. For a symmetric matrix, eig returns real eigenvalues in ascending order and orthonormal eigenvectors, which makes symmetric problems (vibrations, principal component analysis, covariance matrices) especially well behaved. And svd(A), the singular value decomposition, works for any matrix, square or not: the ratio of the largest to the smallest singular value is exactly cond(A), the number of singular values above a small tolerance is the rank (this is how rank is computed), and keeping only the largest ones gives the best low-rank approximation of a matrix, the idea behind many compression and recommendation methods.

ComputationC

Worked example: a sparse system with ten thousand unknowns

Matrices that come from physical models are usually sparse: almost all their entries are zero, because each point in a model interacts only with its neighbours. Storing the zeros would waste memory, and computing with them would waste time. A sparse matrix in MATLAB and Octave stores only the nonzero entries and their positions, and every operation in this lesson, backslash included, works on it.

Here is a classic example: the steady temperature along a thin rod held at temperature zero at both ends and heated along its length. The temperature u(x)u(x) satisfies −u′′(x)=f(x)-u''(x) = f(x). Replacing u′′u'' at each of nn grid points by the finite difference (ui−1−2ui+ui+1)/h2(u_{i-1} - 2u_i + u_{i+1})/h^2, where hh is the grid spacing, turns the differential equation into a linear system whose matrix has only three nonzero diagonals:

matlab
% Steady temperature in a rod: -u''(x) = f(x) on 0 < x < 1, u(0) = u(1) = 0,
% with heating f(x) = pi^2 sin(pi x). The exact answer is u(x) = sin(pi x).
for n = [9 99 999 9999]              % number of interior grid points
  h = 1 / (n + 1);
  x = (1:n)' * h;
  e = ones(n, 1);
  K = spdiags([-e 2*e -e], [-1 0 1], n, n) / h^2;   % tridiagonal, sparse
  f = pi^2 * sin(pi * x);
  u = K \ f;
  err = max(abs(u - sin(pi * x)));
  fprintf('n = %5d: max error %.2e, nonzeros %6d of %10d\n', n, err, nnz(K), n^2);
end
disp(full(K(1:4, 1:4)) * h^2)
text
n =     9: max error 8.27e-03, nonzeros     25 of         81
n =    99: max error 8.23e-05, nonzeros    295 of       9801
n =   999: max error 8.22e-07, nonzeros   2995 of     998001
n =  9999: max error 8.24e-09, nonzeros  29995 of   99980001
   2  -1   0   0
  -1   2  -1   0
   0  -1   2  -1
   0   0  -1   2

The heating was chosen so that the exact temperature is known, sin⁡(πx)\sin(\pi x), which lets the program measure its own error, a habit worth copying whenever you test a numerical method. Three lessons hide in the output:

  • Sparsity is what makes this feasible. With 9,999 unknowns, the full matrix would have about 10810^8 entries, 800 MB of doubles; the sparse one stores 29,995. spdiags builds a sparse matrix from its diagonals; sparse(i, j, v, m, n) builds one from lists of positions and values; speye is the sparse identity; full converts back for display.
  • Backslash recognises the structure. For a sparse tridiagonal matrix it uses a banded solver whose cost grows in proportion to n, so the 9,999-unknown system solves in a blink.
  • The error falls a hundredfold each time the grid becomes ten times finer. That is the signature of a second-order method: error proportional to h2h^2. Measuring how error falls with the step size is how numerical analysts check that a method is implemented correctly, and you will do it again in the next lesson.

For two- and three-dimensional problems with millions of unknowns, direct sparse solvers eventually run out of memory too, and iterative methods such as the conjugate gradient method (pcg) and GMRES (gmres), both available in MATLAB and Octave, take over. They never factorise the matrix; they only multiply by it.

Common misconceptionsH

Common misconceptions

Misconception

"x = inv(A) * b is the natural way to solve a system." It is slower and less accurate than A \ b, and for sparse matrices it can be catastrophically expensive. Reserve inv for the rare case where you need the entries of the inverse itself.

Misconception

"A tiny residual means the solution is accurate." Backslash always makes the residual tiny. The accuracy of x depends on the condition number as well. Check cond or rcond when the matrix might be badly conditioned.

Misconception

"If det(A) is close to zero, the matrix is nearly singular." The determinant scales with the size of the entries: det(0.1 * eye(100)) is 10−10010^{-100} for a perfectly conditioned matrix. Use rcond, cond or rank.

Misconception

"A \ b and b / A are the same thing." A \ b solves A*x = b for a column x; b / A solves x*A = b for a row x. With a square matrix and the wrong orientation, you either get an error or the solution of a different problem.

Misconception

"A model that curves cannot be fitted with linear least squares." "Linear" refers to the unknown coefficients, not to the shape of the curve. A quadratic, a sum of sines or the stopping-distance model above are all fitted with one backslash. Only models where the unknowns sit inside a nonlinear function, such as an unknown rate in e−kte^{-kt}, need the iterative methods of the next lesson.

Exercises

Exercises

1. Linear algebra and linear systems

Warm-upComputational

A is a square nonsingular matrix and b a column vector. Which expression is the recommended way to compute the column x with A*x = b?

Choose one

2. Linear algebra and linear systems

Warm-upComputational

What does this display?

x = [2 0; 0 4] \ [6; 8];
disp(sum(x))

3. Linear algebra and linear systems

CoreComputational

What does disp([1; 1; 1] \ [2; 4; 9]) display?

4. Linear algebra and linear systems

Warm-upComputational

What does this print?

p = polyfit([0 1 2], [1 3 5], 1);
fprintf('%.1f %.1f\n', p);

5. Linear algebra and linear systems

CoreHuman

You solve x = A \ b. The relative residual norm(A*x - b) / norm(b) is about 1e-16 and cond(A) is about 1e12. Roughly how many significant digits of x can you trust?

Choose one

6. Linear algebra and linear systems

StretchHuman

Which of these are sound ways to check, in a program, whether a square matrix A is singular or nearly singular? Choose all that apply.

Choose all that apply

7. Linear algebra and linear systems

StretchComputational

A bike scheme has two docks. Each day 10% of the bikes at dock 1 move to dock 2, and 20% of those at dock 2 move to dock 1:

P = [0.9 0.1; 0.2 0.8];

Starting with 300 bikes, all at dock 1, how many are at dock 1 in the long run (after many days of bikes = bikes * P)?

8. Linear algebra and linear systems

CoreComputational

How many nonzero entries does this 5-by-5 sparse matrix have? That is, what does disp(nnz(K)) show?

K = spdiags(ones(5, 3), [-1 0 1], 5, 5);

Further reading and resources