lacunary - Mathnotes

Matrices

Matrix Multiplication

Definition: matrix product (also: product, matrix multiplication) \@{matrix-product}

Let A be an m×n matrix and B be an n×p matrix. We define the product of A an B, denoted AB, to be the m×p matrix such that

(AB)i,j=∑k=1nAi,kBk,jfor 1≤i≤m,1≤j≤p.

Note \@{note-3}

(AB)i,j is the @sum of products of corresponding entries from the ith @row of A and the jth @column of B.

The following mnemonic is helpful:

(m×n)⋅(n×p)=(m×p).

Remark: The Four Ways to View Matrix Multiplication \@{remark-4}

We can view the matrix product AB=C in (at least) four different ways:

  1. Each entry of C is a dot product: The entry Ci,j=(row i of A)⋅(column j of B)=∑k=1nAi,kBk,j.
  2. Each column of C is A times the corresponding column of B: C⋅,j=AB⋅,j, so C⋅,j=B1,jA⋅,1+⋯+Bn,jA⋅,n In other words, the columns of C are linear combinations of the columns of A.
  3. Each row of C is the corresponding row of A multiplied by B: Ci,⋅=Ai,⋅B, so Ci,⋅=Ai,1B1,⋅+⋯+Ai,nBn,⋅. In other words, the rows of C are linear combinations of the rows of B.
  4. C is a sum of column × row outer products: C=AB=a1b1⊤+asb2⊤+⋯+anbn⊤.

The Four Fundamental Subspaces

Definition: Four Fundamental Subspaces (also defines: Column space, Nullspace, Row space, left nullspace) \@{four-fundamental-subspaces}

Any m×n matrix A determines four @subspaces (each possibly containing only the zero vector):

  • The Column space, denoted C(A), consists of all linear combinations of the columns of A and is a vector in Rm.
  • The Nullspace, denoted N(A), consists of all solutions x of the equation Ax=0 and is a subspace of Rn.
  • The Row space, denoted C(A⊤), consists of all linear combinations of the rows of A and forms a subspace of Rn. We equate this with C(A⊤), the column space of the @transpose of A.
  • The left nullspace, denoted N(A⊤), which is a subspace of Rm.
Referenced by (5 direct)

Direct references:

Theorem: Basis and Dimension for Column Space \@{basis-and-dimension-for-column-space}

For an m×n matrix with r=rankA, the r @pivot columns form a @basis for the column space C(A) and dim⁡C(A)=r.

Theorem: Basis and Dimension for Nullspace \@{basis-and-dimension-for-nullspace}

For an m×n matrix with r=rankA, the @special solutions to Ax=0 correspond to @free variables and form a @basis for the nullspace N(A). An m×n matrix has n−r free variables, so dim⁡N(A)=n−r.

Theorem: Basis and Dimension for Row Space (also defines: echelon basis) \@{basis-and-dimension-for-row-space}

For an m×n matrix with r=rankA, let R be the @reduced echelon form of A. The row space of R is the same as the row space of A - the rows of A are linear combinations of the rows of R.

The first r rows of R are the echelon basis for the row space of A and dim⁡C(A⊤)=r.

Referenced by (1 direct)

Direct references:

Theorem: Basis and Dimension for Left Nullspace \@{basis-and-dimension-for-left-nullspace}

For an m×n matrix with r=rankA, we know from Basis and Dimension for Row Space that r is the rank of A⊤, so the number of @free columns of A⊤ must be m−r and dim⁡N(A⊤)=m−r.

The left nullspace is the collection of vectors y for which A⊤y=0. Equivalently, y⊤A=0, with y and 0 row vectors - this is why we say left nullspace. To find a basis for the left nullspace we reduce an @augmented version of A:

[Am×nIm×n]→[Rm×nEm×n].

From this we get the matrix E for which EA=R, and if A is a @square, @invertible matrix, then E=A−1. The bottom m−r rows of E satisfy the equation y⊤A=0 and form a basis for the left nullspace of A.

Theorem: Row space and nullspace are orthogonal complements \@{row-space-and-nullspace-are-orthogonal-complements}

The row space and nullspace are orthogonal complements. That is,

  • C(A⊤)=N(A)⊥ (orthogonal components in Rn)
  • N(A⊤)=C(A)⊥ (orthogonal components in Rm)

In other words, each x in the nullspace is orthogonal to each row, which comes directly from Ax=0:

Ax=0[(row 1)⋯(row m)][ x ]=[0⋯0]⟵x is orthogonal to row 1 ⟵x is orthogonal to row m