Day 17: Matrix Multiplication, Transpose & the Design Matrix

Theory

The product

If $A$ is $m \times n$ and $B$ is $n \times p$ , the product $C = AB$ is $m \times p$ with

c_{ij} = \sum_{\ell=1}^n a_{i\ell}b_{\ell j} = (\text{row } i \text{ of } A) \cdot (\text{column } j \text{ of } B).

The inner dimensions must match ("conformable"). Matrix multiplication is associative and distributive but not commutative: in general $AB \ne BA$ , and one of them may not even exist.

Two ways to read Ax

Ax = \sum_{j} x_j\,a_{\cdot j}

is a linear combination of the columns of $A$ with weights $x_j$ . So $X\beta$ , the vector of fitted values, is " $\beta_0$ times the intercept column plus $\beta_1$ times the education column plus …". Alternatively, entry $i$ of $Ax$ is row $i$ of $A$ dotted with $x$ : unit $i$ 's prediction.

A matrix also acts as a linear transformation: it maps vectors to vectors, preserving sums and scalar multiples. In 2D you can watch it stretch, rotate, shear or flip the plane (Simulation Lab).

Transpose and trace

(AB)^{\top} = B^{\top}A^{\top}, \qquad \operatorname{tr}(A) = \sum_i a_{ii}, \qquad \operatorname{tr}(AB) = \operatorname{tr}(BA).

The cross-product matrices

For a design matrix $X$ ( $n \times k$ ) and outcome $y$ ( $n \times 1$ ):

X^{\top}X = \Big[\sum_i x_{ij}x_{i\ell}\Big]_{j,\ell}, \qquad X^{\top}y = \Big[\sum_i x_{ij}y_i\Big]_{j}.

With an intercept and one regressor,

X^{\top}X = \begin{pmatrix} n & \sum x_i \\ \sum x_i & \sum x_i^2 \end{pmatrix}, \qquad X^{\top}y = \begin{pmatrix} \sum y_i \\ \sum x_iy_i \end{pmatrix}.

On Day 27 the OLS estimator will be $\hat\beta = (X^{\top}X)^{-1}X^{\top}y$ : everything it needs is in these two objects.

The centring matrix

M_{\mathbf 1} = I_n - \tfrac1n\mathbf{1}\mathbf{1}^{\top}, \qquad M_{\mathbf 1}y = y - \bar y\mathbf{1}.

Multiplying by $M_{\mathbf 1}$ subtracts the mean, the matrix version of "demeaning", which becomes fixed-effects estimation on Day 28.

Part 1 · Warm-up

Exercise 1 · Order matters

Let $A = \begin{pmatrix}1 & 2\\3 & 4\end{pmatrix}$ and $B = \begin{pmatrix}0 & 1\\1 & 0\end{pmatrix}$ . Compute $AB$ and $BA$ .

Show solution

$AB = \begin{pmatrix}2 & 1\\4 & 3\end{pmatrix}$ (columns of $A$ swapped), $BA = \begin{pmatrix}3 & 4\\1 & 2\end{pmatrix}$ (rows swapped). They differ.

Exercise 2 · Conformability

$A$ is $2 \times 3$ and $B$ is $3 \times 4$ . Which of $AB$ , $BA$ , $A^{\top}A$ , $B^{\top}A^{\top}$ exist, and what shapes are they?

Show solution

Step 1. $AB$ : $2 \times 4$ .

Step 2. $BA$ : not defined ( $4 \ne 2$ ).

Step 3. $A^{\top}A$ : $3 \times 3$ .

Step 4. $B^{\top}A^{\top}$ : $4 \times 2$ (it equals $(AB)^{\top}$ ).

Exercise 3 · Columns, combined

$A = \begin{pmatrix}1 & 2\\3 & 1\end{pmatrix}$ , $x = (1, 1)^{\top}$ . Compute $Ax$ both row-by-row and as a combination of columns.

Show solution

Rows: $(1 + 2,\; 3 + 1) = (3, 4)$ . Columns: $1\cdot(1, 3) + 1\cdot(2, 1) = (3, 4)$ .

Exercise 4 · Transpose of a product

Check $(AB)^{\top} = B^{\top}A^{\top}$ for the matrices in Exercise 1.

Show solution

$(AB)^{\top} = \begin{pmatrix}2 & 4\\1 & 3\end{pmatrix}$ . $B^{\top}A^{\top} = \begin{pmatrix}0 & 1\\1 & 0\end{pmatrix}\begin{pmatrix}1 & 3\\2 & 4\end{pmatrix} = \begin{pmatrix}2 & 4\\1 & 3\end{pmatrix}$ . ✓

Exercise 5 · Trace

Compute $\operatorname{tr}(A)$ , $\operatorname{tr}(AB)$ and $\operatorname{tr}(BA)$ for Exercise 1.

Show solution

$\operatorname{tr}(A) = 5$ , $\operatorname{tr}(AB) = 2 + 3 = 5$ , $\operatorname{tr}(BA) = 3 + 2 = 5$ . Equal even though $AB \ne BA$ .

Part 2 · Proofs

Exercise 6 · Transpose of a product

Prove $(AB)^{\top} = B^{\top}A^{\top}$ .

Show solution

$[(AB)^{\top}]_{ij} = (AB)_{ji} = \sum_\ell a_{j\ell}b_{\ell i} = \sum_\ell (B^{\top})_{i\ell}(A^{\top})_{\ell j} = (B^{\top}A^{\top})_{ij}$ .

Exercise 7 · Cyclic trace

Prove $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ for $A$ ( $m \times n$ ) and $B$ ( $n \times m$ ).

Show solution

$\operatorname{tr}(AB) = \sum_i\sum_\ell a_{i\ell}b_{\ell i} = \sum_\ell\sum_i b_{\ell i}a_{i\ell} = \operatorname{tr}(BA)$ . Day 20 uses this to show $\operatorname{tr}(P) = k$ .

Exercise 8 · The structure of X′X

Show that $X^{\top}X$ is symmetric, that its diagonal holds the sums of squares of the columns, and derive its form with an intercept and one regressor.

Show solution

Step 1. $(X^{\top}X)^{\top} = X^{\top}(X^{\top})^{\top} = X^{\top}X$ .

Step 2. Entry $(j, \ell)$ is column $j$ dotted with column $\ell$ , so the diagonal is $\sum_i x_{ij}^2$ .

Step 3. With columns $\mathbf 1$ and $x$ : $\mathbf 1^{\top}\mathbf 1 = n$ , $\mathbf 1^{\top}x = \sum x_i$ , $x^{\top}x = \sum x_i^2$ .

Exercise 9 · Quadratic forms

Show that $u^{\top}Au = \sum_i\sum_j a_{ij}u_iu_j$ , and write $u^{\top}Au$ for $A = \begin{pmatrix}2 & 1\\1 & 3\end{pmatrix}$ .

Show solution

$(Au)_i = \sum_j a_{ij}u_j$ , so $u^{\top}Au = \sum_i u_i\sum_j a_{ij}u_j$ . Here $u^{\top}Au = 2u_1^2 + 2u_1u_2 + 3u_2^2$ (the off-diagonal 1 appears twice).

Exercise 10 · X′X is positive semi-definite

Show that $v^{\top}X^{\top}Xv \ge 0$ for every $v$ .

Show solution

Step 1. $v^{\top}X^{\top}Xv = (Xv)^{\top}(Xv) = \|Xv\|^2 \ge 0$ .

Step 2. It is zero only if $Xv = 0$ , i.e. if some combination of the columns vanishes: the collinearity problem of Day 18.

Part 3 · Applied

Exercise 11 · Cross-products from data

An agricultural extension service records, for four farms, the number of advisory visits $x = (1, 2, 3, 4)$ and maize yield $y = (2, 3, 5, 6)$ tonnes per hectare. For a regression of yield on an intercept and visits, build $X^{\top}X$ and $X^{\top}y$ . (Days 20 and 24 reuse these four farms.)

Show solution

Step 1. The design matrix has a column of ones and the visits column, so we need $n$ , $\sum x$ , $\sum x^2$ , $\sum y$ and $\sum xy$ .

Step 2. $n = 4$ , $\sum x = 10$ , $\sum x^2 = 1 + 4 + 9 + 16 = 30$ .

Step 3. $\sum y = 16$ , $\sum xy = 1(2) + 2(3) + 3(5) + 4(6) = 2 + 6 + 15 + 24 = 47$ .

Answer:

X^{\top}X = \begin{pmatrix}4 & 10\\10 & 30\end{pmatrix}, \qquad X^{\top}y = \begin{pmatrix}16\\47\end{pmatrix}.

Exercise 12 · Fitted yields

For the four farms, use $\beta = (0.5, 1.4)^{\top}$ (intercept 0.5 t/ha, 1.4 t/ha per visit). Compute fitted yields $X\beta$ and the residuals $y - X\beta$ .

Show solution

Step 1. Fitted yield $= 0.5 + 1.4x$ : $1.9,\; 3.3,\; 4.7,\; 6.1$ .

Step 2. Residuals $= y - \hat y$ : $2 - 1.9 = 0.1$ , $3 - 3.3 = -0.3$ , $5 - 4.7 = 0.3$ , $6 - 6.1 = -0.1$ .

Step 3. Checks: $\sum e = 0$ and $\sum x_ie_i = 0.1 - 0.6 + 0.9 - 0.4 = 0$ .

Answer: $\hat y = (1.9, 3.3, 4.7, 6.1)$ and $e = (0.1, -0.3, 0.3, -0.1)$ . The zero sums are no accident: $(0.5, 1.4)$ is the OLS solution (Day 27).

Exercise 13 · A treatment dummy

A sample has $n = 10$ units of which $n_1 = 4$ are treated. Write $X^{\top}X$ for a regression on an intercept and the treatment dummy $T$ .

Show solution

Step 1. Entries: $n = 10$ ; $\sum T_i = 4$ ; $\sum T_i^2 = 4$ (because $T^2 = T$ for a 0/1 variable).

Answer:

X^{\top}X = \begin{pmatrix}10 & 4\\4 & 4\end{pmatrix}.

Exercise 14 · Demeaning household incomes

Three households have monthly incomes $y = (1, 2, 6)$ (thousand dollars). Write the centring matrix $M_{\mathbf 1}$ for $n = 3$ and compute $M_{\mathbf 1}y$ .

Show solution

Step 1. $M_{\mathbf 1} = I - \frac13\mathbf 1\mathbf 1^{\top}$ : diagonal entries $1 - \frac13 = \frac23$ , off-diagonal $-\frac13$ :

M_{\mathbf 1} = \frac13\begin{pmatrix}2 & -1 & -1\\-1 & 2 & -1\\-1 & -1 & 2\end{pmatrix}.

Step 2. First entry: $\frac13(2 \cdot 1 - 2 - 6) = -2$ ; similarly the others.

Step 3. Equivalently, subtract the mean $\bar y = 3$ : $(1 - 3, 2 - 3, 6 - 3)$ .

Answer: $M_{\mathbf 1}y = (-2, -1, 3)$ : each household's income relative to the average.

Exercise 15 · Computing X′y for a large survey

A survey has $n = 1000$ households and $k = 3$ regressors, so $X^{\top}$ is $3 \times 1000$ , $X$ is $1000 \times 3$ and $y$ is $1000 \times 1$ . Software must compute $X(X^{\top}y)$ (needed for fitted values). Compare the multiplications needed for $(XX^{\top})y$ and $X(X^{\top}y)$ .

Show solution

Step 1. $(XX^{\top})y$ : forming $XX^{\top}$ ( $1000 \times 1000$ ) costs $1000 \times 1000 \times 3 = 3{,}000{,}000$ multiplications.

Step 2. Multiplying that by $y$ costs another $1000 \times 1000 = 1{,}000{,}000$ : total about 4 million.

Step 3. $X(X^{\top}y)$ : $X^{\top}y$ ( $3 \times 1$ ) costs $3 \times 1000 = 3{,}000$ .

Step 4. Then $X$ times a $3 \times 1$ vector costs $1000 \times 3 = 3{,}000$ : total 6,000.

Answer: same result, about 700 times cheaper, which is why software never builds an $n \times n$ matrix when it can avoid it.

Verify in Python

import numpy as np

A = np.array([[1, 2], [3, 4]]); B = np.array([[0, 1], [1, 0]])
print("AB =\n", A @ B, "\nBA =\n", B @ A)
print("(AB)' == B'A':", np.array_equal((A @ B).T, B.T @ A.T), " tr(AB), tr(BA):", np.trace(A @ B), np.trace(B @ A))

x = np.array([1, 2, 3, 4.]); y = np.array([2, 3, 5, 6.])
X = np.column_stack([np.ones(4), x])
print("X'X =\n", X.T @ X, "\nX'y =", X.T @ y)
beta = np.array([0.5, 1.4]); e = y - X @ beta
print("residuals:", e.round(2), " X'e =", (X.T @ e).round(10))

n = 3; M = np.eye(n) - np.ones((n, n)) / n
print("M y =", M @ np.array([1, 2, 6.]))

Key takeaways

$Ax$ is a weighted combination of the columns of $A$ ; $X\beta$ is the vector of fitted values.
$(AB)^{\top} = B^{\top}A^{\top}$ and $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ are used constantly in proofs.
$X^{\top}X$ and $X^{\top}y$ hold all the sums of squares and cross-products that regression needs.

Day 17. Matrix Multiplication, Transpose & the Design Matrix

Theory

The product

Two ways to read Ax

Transpose and trace

The cross-product matrices

The centring matrix

Part 1 · Warm-up

Exercise 1 · Order matters

Exercise 2 · Conformability

Exercise 3 · Columns, combined

Exercise 4 · Transpose of a product

Exercise 5 · Trace

Part 2 · Proofs

Exercise 6 · Transpose of a product

Exercise 7 · Cyclic trace

Exercise 8 · The structure of X′X

Exercise 9 · Quadratic forms

Exercise 10 · X′X is positive semi-definite

Part 3 · Applied

Exercise 11 · Cross-products from data

Exercise 12 · Fitted yields

Exercise 13 · A treatment dummy

Exercise 14 · Demeaning household incomes

Exercise 15 · Computing X′y for a large survey

Verify in Python

Key takeaways

Simulation Lab: A Matrix as a Transformation