These are all True Facts and some of them might be helpful in this course, particularly on assignments or questions from the course notes. They’re all common knowledge to those familiar with linear algebra, but (understandably) you may have forgotten them since your last linear algebra course, or never seen them articulated in useful forms.
However, all of them are presented without proof, and the starred ones would need to be proved if you’d like to use them in an assignment or on a test.
If you would like an additional resource on linear algebra, I would highly recommend Linear Algebra Done Right by Sheldon Axler.
Matrices
RCA
An $m \times n$ matrix $M \in \R^{m \times n}$ has $m$ rows and $n$ columns, and $M_{ij}$ is the entry on the entry on the $i$th row and $j$th column. We always describe matrices in the RCA order:
- Rows
- Columns
- A doesn’t stand for anything
Matrix-vector product
Let $M \in \R^{m \times n}$ be a matrix whose columns are $\curlies{\m_1, \cdots, \m_n} \subset \R^n$, and let $\x = (x_1, \cdots, x_n) \in \R^n$ be a vector. Then $M\x \in \R^m$ and it is a linear combination of the columns of $M$.
\[M \x = x_1 \m_1 + \cdots + x_n \m_n\]Let $\curlies{\m^1, …, \m^m}$ be the rows of $M$. Then, the $i$th entry of $M\x$ is the dot product $(M\x)_i = \m^i \cdot \x$.
\[M\x = \begin{pmatrix} \m^1 \cdot \x \\ \vdots \\ \m^m \cdot \x \end{pmatrix}\]Matrix-matrix product
Let $M \in \R^{\ell \times m}$ have rows $\curlies{\m^1, \cdots, \m^\ell}$ and $N \in \R^{m \times n}$ have columns $\curlies{\n_1, \cdots, \n_n}$. Then $MN \in \R^{\ell \times n}$, and the $j$th column of $MN$ is $M\n_j$, so the $ij$th entry of $MN$ is $(MN)_{ij} = \m^i \cdot \n_j$.
\[\begin{align*} MN &= \begin{pmatrix} | & & | \\ M \n_1 & \cdots & M \n_n \\ | & & | \end{pmatrix} \\ &= \begin{pmatrix} \m^1 \cdot \n_1 & \cdots & \m^1 \cdot \n_n \\ \vdots & & \vdots \\ \m^\ell \cdot \n_1 & \cdots & \m^\ell \cdot \n_n \\ \end{pmatrix} \\ \end{align*}\]Transposes
Transpose of product switches order
\[(MN)^\top = N^\top M^\top\]The dot product using transpose
For $\x, \y \in \R^n$ \(\x \cdot \y = \x^\top \y\)
The dot product for vectors in $\R^n$ is also called the inner product - this corresponds to how
- the $^\top$ is in between the $\x$ and the $\y$, i.e. it is inner
- as matrices, $\x^\top$ is $1 \times n$ matrix and $\y$ is $n \times 1$, and their product is $(1 \times n) \cdot (n \times 1) = 1 \times 1$, as $n$ is the inner dimension
The outer product
For $\x = (x_1, \cdots, x_m) \in \R^m, \y \in \R^n$,
\[\x\y^\top \in \R^{m \times n}\]This is called the outer product, for similar reasons to why the previous one is called the inner product. Notice that though the notation is similar, this is very different! An inner product is a scalar, while an outer product is a matrix.
You can calculate the outer product just like any matrix product, and what you’ll get is
\[\x\y^\top = \begin{pmatrix} | & & | \\ x_1 \y & \cdots & x_m \y \\ | & & | \end{pmatrix}\]You can also think of this as an inner product that is “deferred” to later. Suppose $M = \x\y^\top$ and $\z \in \R^n$, then
\[\begin{align*} M\z &= (\x \y^\top) \z \\ &= \x (\y^\top \z) \\ &= \underbrace{(\y \cdot \z)}_{\in \R} \x \end{align*}\]The transpose and the dot product ($\star$)
\[\x \cdot M\y = M^\top \x \cdot \y \tag{$\star$}\]$A^\top A$ is a positive matrix ($\star$)
\[\x \cdot (A^\top A \x) \geq 0 \tag{$\star$}\]Isometries ($\star$)
Let $M \in \R^{n \times n}$ be a matrix, then the following are equivalent:
\[\begin{align*} \norm{M \x} &= \norm \x \text{ for all } \x \in \R^n \\ &\Updownarrow \\ M \x \cdot M \y &= \x \cdot \y \text{ for all } \x, \y \in \R^n \tag{$\star$} \\ &\Updownarrow \\ M^\top &= \inv M \end{align*}\]The first line can be interpreted as “applying $M$ doesn’t change the size of $\x$”. The second can be interpreted as “$M$ treats all vectors the same way”. Overall, your intuition for an isometry should be “something like a rotation”.
Permutation matrices are isometrices ($\star$)
In particular, if $P \in \R^{n \times n}$ is a permutation matrix (i.e. if the columns of $P$ are some permutation of the standard basis vectors ${\e_1, …, \e_n}$) then $P^\top = \inv P$. ($\star$)
Spectral theorem
Let $M \in \R^{n \times n}$ be a square matrix. If $M = M^\top$, then there exists a basis
\[\mathcal B = \{\v_1, ..., \v_n \} \subseteq \R^n\]such that each $\v_i$ is an eigenvector of $M$, and any pair of them has dot product $\v_i \cdot \v_j = 0$ for $i \neq j$.
Norms
Cauchy-Schwarz inequality
\[\abs{\x \cdot \y} \leq \norm{\x} \norm{\y}\]Triangle inequality
\[\norm{\x + \y} \leq \norm \x + \norm \y\]Pythagoras
\[\x \cdot \y = 0 \implies \norm{\x + \y}^2 = \norm{\x}^2 + \norm y^2\]Eigenvalues and eigenvectors
Eigenvalues of inverse ($\star$)
Let $\lambda \in \R$ be an eigenvalue of $M \in \R^{n \times n}$. Then, $\dfrac{1}{\lambda}$ is an eigenvalue of $\inv M$ (if $\inv M$ exists). ($\star$)