Linear Algebra (1): Ax = b

flowchart TD
  A["Ax = b"] --> B["Vector Space"]
  B --> C["Subspace"]
  C --> D["Linear Combination"]
  D --> E["Span"]
  E --> F["Column Space"]
  E --> G["Null Space"]
  F --> H["Linear Independence"]
  G --> H
  H --> I["Basis and Dimension"]
  I --> J["Rank–Nullity Theorem"]
  J --> K["Solutions of Ax = b"]

Ax = b

Setup. A system of linear equations in unknowns is written , where

is the coefficient matrix,
is the vector of unknowns,
is the right-hand side.

Definitions.

Augmented matrix: .
Consistent: the system has at least one solution. Otherwise it is inconsistent.
Row echelon form (REF): every zero row is at the bottom, and the leading (first non-zero) entry of each row lies to the right of the leading entry of the row above it.
Pivot: a leading entry of REF. A pivot column is a column that contains a pivot.
Basic variable: a variable whose column is a pivot column. Free variable: a variable whose column is not.

Questions. Does a solution exist? Is it unique? What do all the solutions look like? The boxes below build the tools; the last box answers them.

Vector Space

Definition. A vector space is a set with two operations, addition and scalar multiplication, such that the following 10 axioms hold for all and all scalars .

Addition

Closure:
Commutativity:
Associativity:
Zero vector: there is a with
Additive inverse: each has a with

Scalar multiplication

Closure:
Distributivity over vectors:
Distributivity over scalars:
Associativity:
Identity:

Examples.

Space	Elements
	columns of real numbers
	polynomials of degree at most
	real matrices
	continuous functions on

Subspace

Definition. A subspace of is a subset that is itself a vector space under the operations of .

Subspace test. is a subspace if and only if

Zero vector:
Closure under addition:
Closure under scalar multiplication:

The other axioms are inherited from .

Non-example. is not a subspace: it is not closed under scalar multiplication, since .

Linear Combination

Definition. A linear combination of is a vector of the form

The scalars are the weights.

Span

Definition. The span of is the set of all their linear combinations:

Properties.

is always a subspace of .
If spans , then so does

Column Space

Definition. For with columns , the column space of is

Remark. is a linear combination of the columns of , with the entries of as weights:

Theorem. is consistent

Null Space

Definition. For , the null space of is

Properties.

is a subspace of .
If is one solution of , then every solution has the form with .

Linear Independence

Definition. is linearly independent if

Otherwise it is linearly dependent: some non-trivial combination gives , so one of the vectors is a linear combination of the others.

No redundancy: the only combination that gives is the trivial one.

Theorem. For , the following are equivalent:

the columns of are linearly independent;
;
has only the trivial solution.

Example. If is linearly independent, then so is .

Since is independent, and , so .

Basis and Dimension

Definition. A basis of is a set of vectors in that

is linearly independent, and
spans .

Theorem. If is a basis of , every can be written as in exactly one way.

Definition. The dimension of , , is the number of vectors in a basis of . Every basis of has the same number of vectors.

Definition. The row space of is = span of the rows of .

Finding a basis.

Space	Basis
	the pivot columns of the original
	one vector per free variable, from the solution of
	the non-zero rows of REF

Example. . The condition forces a zero diagonal and :

The three matrices form a basis, so .

Rank–Nullity Theorem

Definitions. For :

= number of pivots
= number of free variables

Theorem (Rank–Nullity).

Equivalently: number of pivots + number of free variables = number of columns = number of unknowns.

Solutions of Ax = b

For :

Space	What it answers
	Existence: a solution exists
	If consistent, how many equations are necessary to solve it:
	Uniqueness and the form of all solutions:

Property	REF	Rank	Space
consistent for every	a pivot in every row
at most one solution	a pivot in every column, no free variables

Corollary. has exactly one solution for every , that is, is square and invertible.