Linear Dependence and Span

Reaching b along the columns

Last time you solved with an inverse. Now we ask when that works. First surprise: a system never has exactly two solutions.

Suppose and both solve the system. Mix them with any real number :

Drag the two black points along the line of solutions, then slide . Go past both ends.

At you get , at you get , and every other lands somewhere else on the same line. Two solutions therefore force infinitely many. Press Push b off the line to see the other extreme: no solution at all.

Which case do you get?

Think of a toy car with buttons. Button drives it one step along column of . Pressing it times (a negative number reverses) moves the car by steps. The car starts at the origin, the point of all zeros. Here is column :

It is the same product as before, read column by column. Example: columns and with land at .

Your job: choose how far to travel so the violet path ends on the orange diamond . Drag the teal tips or the diamond, or use the sliders.

Now press Parallel columns. Both buttons drive along one line, so you can only reach points on it. Off the line there is no solution. On the line there are many.

Linear combinations and span

Picture a mixing desk with faders. Each fader scales one track and the desk adds them up. In maths, that mix is a linear combination of vectors : scale each by a coefficient and add.

So is a linear combination of the columns of , with the entries of as coefficients. The span of the vectors is every mix you can make.

The span is infinite, so the demo samples it with 700 random mixes (fixed seed). Choose how many vectors to use and drag their tips.

One vector paints a line. Two vectors at a clear angle paint the plane. Squeeze the angle to 0 or 180 degrees and the plane collapses to a line. A vector that is already inside the span of the others adds nothing: it is redundant.

Predict the span

Commit to a guess first. The cloud appears only after you answer.

The column space and the solvability of Ax = b

is always a mix of the columns, so has a solution exactly when is in the span of the columns. That span has two names: the column space or range of .

To solve it for every in , the column space must fill all of . So needs at least columns: .

Try a 3×2 matrix. Its two columns sweep out a flat sheet in 3-D, like a sheet of paper in a room. A solution exists exactly when the target, a fly, lands on the sheet.

With Add a column sticking out the three columns reach all of 3-D, so the gap is always zero. With Add a column inside the plane there are three columns, but the sheet stays a sheet. Having is necessary, not sufficient, as the next section shows.

Linear dependence and independence

Think of a team where one member’s skills are a mix of two colleagues’ skills. That hire adds nothing. Columns can be redundant in the same way. The book’s example is a 2×2 matrix with two identical columns: its column space is only a line, even though .

A set of vectors is linearly independent if no vector in it is a linear combination of the others. Otherwise it is linearly dependent. As a formula the dependent case reads. This formula is added here and is not printed in the book:

To fill , a matrix needs a set of linearly independent columns. The book calls this necessary and sufficient.

The demo lives in the plane, so . Drag the columns and watch the rank, the size of the largest independent set. This name is added here and is not printed in the book.

The requirement is exactly , since no set of -dimensional vectors holds more than independent ones. A wide matrix may hold several such sets. Any one is enough.

Try Identical columns: two columns, rank 1, the book’s example. Try Three, two independent: any of several pairs reaches the whole plane.

Counting solutions and the inverse

Existence is half the story. An inverse also needs at most one solution for every . With more than columns there is more than one way to write each point as a mix of columns, so solutions are not unique. Hence has at most columns. Combined with this leaves : the matrix is square, with all columns independent. A square matrix with dependent columns is singular.

A non-square or singular matrix can still allow solutions, but inversion cannot find them.

Build a matrix by choosing its shape and its rank . The three yes/no lines follow the rule from the argument above.

A solution for every needs rank , and at most one needs rank . So the count is one or infinite, never two.

Left and right inverses

The book also defines an inverse multiplied on the right:

For square matrices the two are the same. For a non-square matrix they differ. This is added here and is not in the book. A tall full-column-rank matrix has with but no right inverse. A wide full-row-rank matrix has but no left inverse:

Edit the six numbers of a 3×2 matrix. The tall tab uses it as is. The wide tab uses its transpose, a 2×3 matrix.

The demo uses the formulas and . Neither formula is in the book. They need the matrix inside the parentheses to be invertible, which is exactly when the columns (or rows) are independent. The side that works gives an identity matrix. The other side cannot, because a tall matrix reaches only a plane of 3-D space.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 2.4 (pages 37–39), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.