Title: Linear Algebra

Q: Hadamard product
A: The Hadamard or Schur product is the elementwise product
\[(\mathbf{s}\odot \mathbf{t})_j = s_jt_j.\]

Q: Vectorisation of a matrix
A: We stack the columns of the matrix to form a column vector:
\[
\operatorname{vec}(A)=\left[a_{1,1}, \ldots, a_{m, 1}, a_{1,2}, \ldots, a_{m, 2}, \ldots, a_{1, n}, \ldots, a_{m, n}\right]^{\mathrm{T}}
\]

Q: Tensor product
A: The tensor product \(V \otimes W\) of two vector spaces \(V\) and \(W\) is a vector space to which is associated a bilinear map \(V \times W \rightarrow V \otimes W\) that maps a pair \((v, w), v \in V, w \in W\) to an element of \(V \otimes W\) denoted \(v \otimes w\).
The tensor product of two vectors is defined from their decomposition on the bases, i.e., if
\[
x=\sum_{b \in B_V} x_b b \in V \quad \text { and } \quad y=\sum_{c \in B_W} y_c c \in W
\]
are vectors decomposed on their respective bases, then the tensor product of \(x\) and \(y\) is
\[
\begin{aligned}
x \otimes y & =\left(\sum_{b \in B_V} x_b b\right) \otimes\left(\sum_{c \in B_W} y_c c\right) \\
& =\sum_{b \in B_V} \sum_{c \in B_W} x_b y_c b \otimes c .
\end{aligned}
\]
E.g. The Kronecker Product gives the Tensor Product for a standard choice of basis

Q: Kronecker Product
A: If \(\mathbf{A}\) is an \(m \times n\) matrix and \(\mathbf{B}\) is a \(p \times q\) matrix, then the Kronecker product \(\mathbf{A} \otimes \mathbf{B}\) is the \(p m \times q n\) block matrix:
\[
\mathbf{A} \otimes \mathbf{B}=\left[\begin{array}{ccc}
a_{11} \mathbf{B} & \cdots & a_{1 n} \mathbf{B} \\
\vdots & \ddots & \vdots \\
a_{m 1} \mathbf{B} & \cdots & a_{m n} \mathbf{B}
\end{array}\right],
\]
or equivalently the elements are given by
\[
(A \otimes B)_{p(r-1)+v, q(s-1)+w}=a_{r s} b_{v w}.
\]

Q: Kronecker mixed product property
A: If \(A, B, C\) and \(D\) are such that the products \(A C\) and \(B D\) are well-defined, then
\[
(A \otimes B)(C \otimes D)=(A C) \otimes(B D)
\]
Proof Suppose \(A\) is \(K \times L\) and \(C\) is \(L \times M\). Then
\[
\begin{aligned}
 (A \otimes B)(C \otimes D)
& =\left[\begin{array}{ccc}
A_{11} B & \ldots & A_{1 L} B \\
\vdots & \ddots & \vdots \\
A_{K 1} B & \ldots & A_{K I} B
\end{array}\right]\left[\begin{array}{ccc}
C_{11} D & \ldots & C_{1 M} D \\
\vdots & \ddots & \vdots \\
C_{L 1} D & \ldots & C_{L M} D
\end{array}\right] \\
A & =\left[\begin{array}{cccc}
\left(\sum_{l=1}^L A_{1 l} C_{l 1}\right) B D & \ldots & \left(\sum_{l=1}^L A_{1 l} C_{l M}\right) B D \\
\vdots & & \ddots & \vdots \\
\left(\sum_{l=1}^L A_{K l} C_{l 1}\right) B D & \ldots & \left(\sum_{l=1}^L A_{K l} C_{l M}\right) B D
\end{array}\right] \\
\mathrm{B} & =\left[\begin{array}{ccc}
(A C)_{11} B D & \ldots & (A C)_{1 M} B D \\
\vdots & \ddots & \vdots \\
(A C)_{K 1} B D & \ldots & (A C)_{K M} B D
\end{array}\right] \\
& =(A C) \otimes(B D).
\end{aligned}
\]

Q: Kronecker vector product identity
A: For any column-vectors \(\mathbf{u}\in\mathbb{R}^m, \mathbf{v}\in\mathbb{R}^n\), we have
\[
\operatorname{vec}\left(\mathbf{u} \mathbf{v}^T\right)=\mathbf{v} \otimes \mathbf{u}.
\]
Proof:
\[
\begin{align*}
\mathbf{u} \mathbf{v}^T &= \left(\begin{array}{c} u_1 \\ \vdots \\ u_m  \end{array} \right) \left( \begin{array}{ccc} v_1 \ldots v_n\end{array} \right) \\
&= \left( \begin{array}{ccc} u_1v_1 & u_1v_2 & \ldots & u_1v_n \\
u_2v_1 & u_2v_2 & \ldots & u_2v_n \\
\vdots & \vdots & \ddots & \vdots \\
u_mv_1 & u_mv_2 & \ldots & u_mv_n
\end{array} \right)  \\
\operatorname{vec} (\mathbf{u} \mathbf{v}^T) &= \left( \begin{array}{ccc} u_1v_1 \\ \vdots \\ u_mv_1 \\ u_1v_2 \\ \vdots \\ u_mv_2 \\ \vdots \\ u_1v_n \\ \vdots \\u_mv_n
\end{array} \right)  \\
&=\left(\begin{array}{c} v_1\mathbf{u} \\ \vdots \\ v_n\mathbf{u}  \end{array} \right) \\
&= \mathbf{v} \otimes \mathbf{u}
\end{align*}
\]

Q: Kronecker Matrix Product identity
A: \[
\operatorname{vec}(A X B) = \left(B^T \otimes A\right) \operatorname{vec}(X)
\]
Proof. Let \(\mathbf{e}_1, \ldots, \mathbf{e}_n\) denote the canonical basis  and \(X=\left(x_{i j}\right)_{i, j=1}^{m, n}\). Using the vector product identity:
\[
\begin{aligned}
\operatorname{vec}(A X B) & =\operatorname{vec}\left(A\left(\sum_{i=1}^m \sum_{j=1}^n x_{i j} \mathbf{e}_i \mathbf{e}_j^T\right) B\right) \\
& =\sum_{i=1}^m \sum_{j=1}^n x_{i j} \operatorname{vec}\left(A \mathbf{e}_i \mathbf{e}_j^T B\right) \\
& =\sum_{i=1}^m \sum_{j=1}^n x_{i j} \operatorname{vec}\left(\left[A \mathbf{e}_i\right]\left[B^T \mathbf{e}_j\right]^T\right) \\
& =\sum_{i=1}^m \sum_{j=1}^n x_{i j}\left[B^T \mathbf{e}_j\right] \otimes\left[A \mathbf{e}_i\right] \\
& =\left(B^T \otimes A\right)\left(\sum_{i=1}^m \sum_{j=1}^n x_{i j} \mathbf{e}_j \otimes \mathbf{e}_i\right) \\
& =\left(B^T \otimes A\right)\left(\sum_{i=1}^m \sum_{j=1}^n x_{i j} \operatorname{vec}\left(\mathbf{e}_i \mathbf{e}_j^T\right)\right) \\
& =\left(B^T \otimes A\right) \operatorname{vec}\left(\sum_{i=1}^m \sum_{j=1}^n x_{i j} \mathbf{e}_i \mathbf{e}_j^T\right)\\
&=\left(B^T \otimes A\right) \operatorname{vec}(X).
\end{aligned}
\]

Q: Rank-one modification
A: We say that \(B\) is a rank-one modification of \(A\) if it differs by a rank 1 matrix:
\[
B = A + uv^T.
\]

Q: ROME
A: Rank-One Model Editing treats an MLP module as a simple key-value store and inserts a new association by making a rank-one change to the weights.
We can test if this change actually edited factual storage by checking generalisation across perturbations of the prompt.

Q: Frobenius norm
A: Definition: \[
\|W\|_F=\sqrt{\mathrm{Tr}(WW^\dagger)} = \sqrt{\sum_{i, j} W_{i, j}^2}
\]
Intuition: assume that \(W\) is diagonalisable, then this becomes the sum of the squares of the eigenvalues. Hence the image of the unit cube has diagonal \(\|W\|_F\) and volume \(\operatorname{det}(W)\).