LLM Primer

Linear Systems

A linear system asks for unknown numbers that satisfy linear equations.

For example:

x+y=5x−y=1\begin{aligned} x + y &= 5 \\ x - y &= 1 \end{aligned}

The solution is x = 3, y = 2.

The same system can be written as a matrix equation:

Ax=bAx = b

Here, A contains the coefficients, x contains the unknowns, and b contains the target values.

There is another useful way to read the same equation:

Can the columns of A, with weights from x, make the target b?

If:

A=[1001],x=[32]A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \quad x = \begin{bmatrix} 3 \\ 2 \end{bmatrix}

then:

Ax=3[10]+2[01]=[32]Ax = 3 \begin{bmatrix} 1 \\ 0 \end{bmatrix} + 2 \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 2 \end{bmatrix}

The input vector x gives the weights. The columns of A are the available directions. The output is what those weighted directions reach.

Three Outcomes

A linear system can have:

  • one solution
  • no solution
  • infinitely many solutions

Geometry explains why. Two lines may cross once, never cross, or be the same line.

The column reading gives the same three outcomes:

  • one solution: there is exactly one way to combine the columns to reach b
  • no solution: no combination reaches b
  • infinitely many solutions: many different combinations reach the same b

In higher dimensions, the picture is harder to draw, but the question is the same.

The number of equations alone does not decide the outcome. What matters is the geometry of the columns and the target. A system with two equations can fail if the target points outside the column space. A system with many unknowns can have many solutions if different inputs produce the same output.

Shape Check

If A has shape m x n, then:

  • x must have length n
  • b must have length m

The input length matches the number of columns. The output length matches the number of rows.

Why ML Cares

Many ML computations are not solved as exact linear systems, but the language is everywhere.

A model asks whether a set of weights can map inputs to targets. A projection asks for the closest reachable point. A least-squares fit asks for the best approximate solution when an exact one may not exist.

MATH-C05-T02-001Exercise: Solve a tiny system

Solve:

x+y=5,x−y=1x + y = 5,\quad x - y = 1

What is x?

Compute it first, then check your number.

Hint

Add the two equations.

Solution

Adding gives (x + y) + (x - y) = 5 + 1, so the y terms cancel and 2x = 6. Therefore x = 3, and substituting back gives y = 2.

MATH-C05-T02-002Exercise: Read the column combination

Let:

A=[1001],x=[4−3]A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \quad x = \begin{bmatrix} 4 \\ -3 \end{bmatrix}

What is Ax?

Compute it first, then check your number.

Hint

The identity matrix keeps the two weights as the two output coordinates.

Solution

The first column gets weight 4, and the second column gets weight -3, so Ax = [4, -3].

MATH-C05-T02-003Exercise: Check the shape

A matrix A has shape 3 x 2. The equation is Ax = b.

How long must b be?

Compute it first, then check your number.

Hint

The output length is the number of rows of A.

Solution

A has 3 rows, so Ax has length 3. Therefore b must also have length 3.

MATH-C05-T02-004Exercise: Spot an unreachable target

Suppose the only available columns are:

a1=[10],a2=[20]a_1 = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \quad a_2 = \begin{bmatrix} 2 \\ 0 \end{bmatrix}

Can any combination of these columns reach [0, 1]?

Answer it first, then check.

Hint

Look at the second coordinate of every possible combination.

Solution

No. Both columns have second coordinate 0, so every combination also has second coordinate 0. The target [0, 1] cannot be reached.

MATH-C05-T02-005Exercise: Interpret many solutions

Enter 1 if a system can have many solutions because different inputs produce the same target output.

Compute it first, then check your number.

Hint

Ask whether the matrix might send some nonzero input direction to zero.

Solution

Enter 1. If some input direction has no effect on the output, then adding that direction to one solution can produce another solution with the same target.

Before Moving On

Read Ax = b as a reachability question: can the matrix A produce the target b from some input x?