Matrix Basics

Span and Basis

$$\mathrm{Span}\{v_1, \ldots, v_n\} = \{a_1 v_1 + \cdots + a_n v_n \mid a_i \in \mathbb{F}\}$$

$v_1, \ldots, v_n$ is a basis of $V$ when

1. the $v_i$ are linearly independent,
2. $\mathrm{Span}\{v_i\} = V$.

If $v_i$ is a basis of $V$, then every $v \in V$ has unique $c_i \in \mathbb{F}$ with $v = c_1 v_1 + \cdots + c_n v_n$. If $v = \sum c_i v_i = \sum c'_i v_i$, subtracting gives

$$\vec{0} = (c_1 - c'_1) v_1 + \cdots + (c_n - c'_n) v_n$$

so $c_i = c'_i$ by linear independence.

Linear Maps

$f : V \to W$ is linear when

$$f(\alpha v + \beta u) = \alpha f(v) + \beta f(u)$$

Any linear $f : \mathbb{F}^n \to \mathbb{F}^m$ is a matrix, namely

$$A = [\, f(e_1) \mid \cdots \mid f(e_n) \,]$$

Nullspace and Range

$$\mathrm{null}(A) = \{x \in \mathbb{F}^n : Ax = \vec{0}\}, \qquad \mathrm{range}(A) = \{Ax : x \in \mathbb{F}^n\}$$ $$\mathrm{nullity}(A) = \dim(\mathrm{null}(A)), \qquad \mathrm{rank}(A) = \dim(\mathrm{range}(A))$$

Columns of $A$ are linearly independent $\iff$ $\mathrm{null}(A) = \{0\}$ $\iff$ $A$ is one-to-one. This is clear from writing $Ax$ as a combination of the columns,

$$Ax = [A_1 | A_2 | \cdots | A_n] \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = x_1 A_1 + \cdots + x_n A_n$$

RREF

A matrix is in reduced row echelon form when

1. the leading entry in every row is 1,
2. each pivot is the only nonzero entry in its column,
3. pivots move to the right going down, and zero rows are at the bottom.

For invertible $A \in M_n(\mathbb{F})$, row reduction solves several systems at once,

$$[A|b] \sim [I|d], \qquad [A|b|b'] \sim [I|d|d']$$

where $Ad = b$ and $Ad' = b'$.

Determinant

$$\det A := \sum_{\sigma} \mathrm{sign}(\sigma) \prod_{i=1}^{n} A_{i,\sigma(i)}$$

where the sum is over all bijections $\sigma : \{1, \ldots, n\} \to \{1, \ldots, n\}$. Also $\det AB = \det A \det B$.

Effects of row operations on $\det A$:

1. swapping two rows multiplies it by $-1$,
2. multiplying a row by $c$ multiplies it by $c$,
3. adding a multiple of one row to another doesn't change it.

Matrix Product and Permutation Matrices

$$(AB)_{ij} = \sum_{k=1}^{n} A_{ik} B_{kj}$$

A permutation matrix has exactly one 1 in every row and every column, and zeros elsewhere. $PA$ permutes the rows of $A$ and $AP^T$ permutes the columns.

Inverse

$B$ is the inverse of $A$ when $AB = BA = I$. For $A \in M_n$ the following are equivalent

1. there is $B$ with $AB = BA = I$,
2. $\det A \neq 0$ $\iff$ $\mathrm{RREF}(A) = I$,
3. $\ker A = \{0\}$ $\iff$ columns of $A$ are linearly independent $\iff$ $A$ is one-to-one,
4. $\mathrm{rank}\, A = n$ $\iff$ columns of $A$ span $\mathbb{F}^n$ $\iff$ $A$ is onto.

Proof

$(1 \Rightarrow 2)$ $AB = I \Rightarrow \det A \det B = 1 \Rightarrow \det A \neq 0$.

$(2 \Rightarrow 1)$ Row operations only multiply the determinant by nonzero constants, so $\det A = c \det(\mathrm{RREF}(A))$ with $c \neq 0$. A square RREF with nonzero determinant has no zero rows, so $\mathrm{RREF}(A) = I$. Row reducing $[A|I] \sim [I|B]$ means $EA = I$ and $E = B$ for a product $E$ of elementary matrices, so $BA = I$, and since $E$ is invertible also $AB = I$.

$(1 \Rightarrow 3)$ $Ax = 0 \Rightarrow BAx = B0 \Rightarrow x = 0$.

$(3, 4 \Rightarrow 1)$ $A$ is one-to-one and onto, so there is an inverse map $B$, which is linear. $ABx = x$ and $BAx = x$ for all $x$, so $AB = BA = I$.

Similarity

$A, B$ are similar when $A = SBS^{-1}$ for some invertible $S$. Similarity is an equivalence relation.