Exercise 1

(Multiplication of block matrices). Consider two block matrices $$ A = \begin{pmatrix} A_{11} & \cdots & A_{1t} \\ \vdots & \ddots & \vdots \\ A_{p1} & \cdots & A_{pt} \end{pmatrix} \quad \text{and} \quad B = \begin{pmatrix} B_{11} & \cdots & B_{1q} \\ \vdots & \ddots & \vdots \\ B_{t1} & \cdots & B_{tq} \end{pmatrix} $$ Moreover, for every $ i \in [p] $, $ j \in [t] $, and $ l \in [q] $ the number of columns of $ A_{ij} $ is equal to the number of rows of $ B_{jl} $. In particular, $ A_{ij} \cdot B_{jl} $ is defined. Prove that $$ A \cdot B = \begin{pmatrix} C_{11} & \cdots & C_{1q} \\ \vdots & \ddots & \vdots \\ C_{p1} & \cdots & C_{pq} \end{pmatrix} $$ with $$ C_{il} = \sum_{j \in [t]} A_{ij} B_{jl} $$ for any $ i \in [p] $ and $ l \in [q] $.

Proof:

Let $ A = (a_{\alpha\beta}) $ and $ B = (b_{\beta\gamma}) $. The entry $ (AB)_{\alpha\gamma} $ is given by $ (AB)_{\alpha\gamma} = \sum_{\beta} a_{\alpha\beta} b_{\beta\gamma} $.

Consider a specific entry $ (C_{il})_{uv} $ within the block $ C_{il} $ of the product matrix $ AB $. This entry corresponds to a global row index $ \alpha $ in $ A $’s $ i $-th block row (specifically, the $ u $-th row within that block row) and a global column index $ \gamma $ in $ B $’s $ l $-th block column (specifically, the $ v $-th column within that block column).

The summation over $ \beta $ can be partitioned according to the column blocks of $ A $ and the row blocks of $ B $ that correspond to the intermediate index $ j $. Specifically, the range of $ \beta $ for which $ a_{\alpha\beta} $ belongs to $ A_{ij} $ and $ b_{\beta\gamma} $ belongs to $ B_{jl} $ forms a segment. Summing these segments yields: $$ (C_{il})_{uv} = \sum_{\beta} a_{\alpha\beta} b_{\beta\gamma} = \sum_{j=1}^{t} \left( \sum_{\substack{\beta_j \in \text{columns of } A_{ij} \\ \text{and rows of } B_{jl}}} (A_{ij})_{u\beta_j} (B_{jl})_{\beta_j v} \right) $$ The inner sum $ \sum_{\beta_j} (A_{ij})_{u\beta_j} (B_{jl})_{\beta_j v} $ precisely represents the $ (u,v) $-th entry of the product matrix $ A_{ij} B_{jl} $.

Therefore, we can write: $$ (C_{il})_{uv} = \sum_{j=1}^{t} (A_{ij} B_{jl})_{uv} $$ Since this equality holds for every entry $ (u,v) $ in the block $ C_{il} $, it follows that the block matrix equation is true: $$ C_{il} = \sum_{j \in [t]} A_{ij} B_{jl} $$

Exercise 2

Let $ P $ be a permutation matrix and consider its column vectors $ p_1, \ldots, p_n $. (i) Prove that each pair of distinct (i.e., $ i \neq j $) $ p_i $ and $ p_j $ are perpendicular. (ii) Prove each $ p_i $ is a unit vector. (iii) Using (i) and (ii) prove that $ P^{-1} = P^T $.

(i)

For distinct columns $ p_i $ and $ p_j $ (where $ i \neq j $), each vector has a single ‘1’ at different positions.

When computing their dot product $ p_i^T p_j = \sum_k (p_i)_k (p_j)_k $, for any given $ k $, at least one of $ (p_i)_k $ or $ (p_j)_k $ must be ‘0’ because their ‘1’s are in different rows. Thus, $ (p_i)_k (p_j)_k = 0 $ for all $ k $, which implies $ p_i^T p_j = 0 $. Therefore, $ p_{i} $ and $ p_j $ are perpendicular for $ i \neq j $.

(ii)

A column vector $ p_i $ has exactly one ‘1’ and all other entries are ‘0’, its norm is $ p_i^T p_i = \sum_k (p_i)_k^2 = 1 $. Therefore, $ \|p_i\| = 1 $, proving $ p_i $ is a unit vector.

(iii)

Consider the entry $ (P^T P)_{ij} $ of the product $ P^T P $. This entry is the dot product of the $ i $-th column of $ P $ with its $ j $-th column: $ (P^T P)_{ij} = p_i^T p_j $.

  • From part (i), if $ i \neq j $, then $ p_i^T p_j = 0 $.
  • From part (ii), if $ i = j $, then $ p_i^T p_i = 1 $.

Thus $ P^T P = I $, therefore, $ P^{-1} = P^T $.

Exercise 3

Let $ A = [a_1, \ldots, a_n] $ be an $ n \times n $ matrix such that $ A^{-1} = A^T $. Prove: (i) Each pair of distinct column vectors $ a_i $ and $ a_j $ are perpendicular. (ii) Each $ a_i $ is a unit vector. Prove that the same is true for the row vectors of $ A $.

(i) & (ii) Proof for Column Vectors

Given $ A^{-1} = A^T $, it follows that $ A^T A = I $.

The entry $ (A^T A)_{kl} $ is the dot product of the $ k $-th column of $ A $ ($ a_k $) and the $ l $-th column of $ A $ ($ a_l $), i.e., $ (A^T A)_{kl} = a_k^T a_l $.

Since $ A^T A = I $, we have:

  • For $ k \neq l $: $ a_k^T a_l = 0 $. This proves that distinct column vectors $ a_k $ and $ a_l $ are perpendicular.
  • For $ k = l $: $ a_k^T a_k = 1 $. This proves that $ \|a_k\|^2 = 1 $, so each column vector $ a_k $ is a unit vector.

Proof for Row Vectors

Let $ A $ have row vectors $ r_1, \ldots, r_n $. From $ A^{-1} = A^T $, it also follows that $ A A^T = I $.

The entry $ (A A^T)_{kl} $ is the dot product of the $ k $-th row of $ A $ ($ r_k $) and the $ l $-th row of $ A $ ($ r_l $), i.e., $ (A A^T)_{kl} = r_k r_l^T $.

Since $ A A^T = I $, we have:

  • For $ k \neq l $: $ r_k r_l^T = 0 $. This proves that distinct row vectors $ r_k $ and $ r_l $ are perpendicular.
  • For $ k = l $: $ r_k r_k^T = 1 $. This proves that $ \|r_k\|^2 = 1 $, so each row vector $ r_k $ is a unit vector.

Exercise 4

Let $ A $ be a square matrix such that there are $ B $ and $ C $ with $ BA = AC = I $. Note we didn’t assume per se $ B = C $. However, prove that $ B = C $. In particular $ A $ is invertible with $ A^{-1} = B = C $.

Proof: $$ \begin{align*} BA & = I \\ (BA)C & = IC = C \\ B(AC)& = C \\ BI = B & = C \end{align*} $$ Thus, $ B $ and $ C $ must be equal. This proves that if both a left inverse and a right inverse exist for a square matrix $ A $, they are unique and identical, defining the inverse $ A^{-1} = B = C $.

Exercise 5

This is intended to repeat what we have learnt in the class. Prove in a vector space: (i) $ 0v = 0 $. (ii) $ (-1)v = -v $. (iii) $ -(v + w) = (-v) + (-w) $. (iv) $ c0 = 0 $. (v) $ c(-v) = (-c)v = -(cv) $.

(i) $$ 0v = (0+0)v = 2\cdot0v \implies 0v = 0 $$ (ii) $$ v + (-1)v = (1 + (-1))v = 0v =0 \implies (-1)v = -v $$ (iii) $$ (v+w) + ((-v) + (-w)) = (v + (-v)) + (w + (-w)) = 0 \implies (-v+w) = (-v) + (-w) $$ (iv) $$ c\cdot \vec{0} = c\cdot(\vec{0} + \vec{0}) = 2(c \cdot \vec{0}) \implies c\cdot \vec{0} = 0 $$ (v) $$ c(-v) = c((-1)v) = (c \cdot (-1))v = (-c)v $$ $$ cv + (-c)v = (c + (-c))v = 0v = 0 \implies (-c)v = -(cv) $$

Combining these, we have $ c(-v) = (-c)v = -(cv) $.