# 區塊矩陣

Block matrix

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

from lingeo import random_int_list

## Main idea

For different purposes, we often partition a matrix into several blocks.
The dimensions of each block should be clear through the context.

The multiplication of two block matrices can be just as expected.
Let

$$
A = \begin{bmatrix}
A_{11} & \cdots & A_{1n} \\
\vdots & ~ & \vdots \\
A_{m1} & \cdots & A_{mn}
\end{bmatrix}
\text{ and }
B = \begin{bmatrix}
B_{11} & \cdots & B_{1\ell} \\
\vdots & ~ & \vdots \\
B_{n1} & \cdots & B_{n\ell}
\end{bmatrix}
$$

such that the width of $A_{1k}$ is the same as the height of $B_{k1}$ for $k = 1,\ldots, n$.
Then $AB$ can be written as a block matrix such that its $ij$-block is

$$
\sum_{k = 1}^n A_{ik} B_{kj}.
$$

For block matrices, one may perform the **block row operations**.

1. swapping: swap the $i$-th and the $j$-th block rows.
Its block elementary matrix $E$ has $\det(E) = (-1)^{m_im_j}$, where $m_i$ and $m_j$ are the number of rows in these two block rows, respectively.
2. rescaling: multiply the $i$-th block row by an invertible matrix $K$.
Its block elementary matrix $E$ has $\det(E) = \det(K)$.
3. row combination: multiply the $j$-th block row by a matrix $K$ and add the result to the $i$-th block row.
Its block elementary matrix $E$ has $\det(E) = 1$.

Similar **block column operations** also apply.

Consider the matrix

$$
M =
\begin{bmatrix}
A & B \\
O & D
\end{bmatrix}.
$$

If both $A$ and $D$ are invertible (sqaure) matrice, one may rescale the first block row and the second block column and get

$$
\begin{bmatrix}
A & B \\
O & D
\end{bmatrix}
=
\begin{bmatrix}
A & O \\
O & I
\end{bmatrix}
\begin{bmatrix}
I & A^{-1}BD^{-1} \\
O & I
\end{bmatrix}
\begin{bmatrix}
I & O \\
O & D
\end{bmatrix}.
$$

Therefore,

$$
\det(M) = \det(A)\det(D).
$$

If $A$ or $D$ is not invertible, then M is also not invertible.
Therefore, the same equality still holds.

$$
\det(M) = \det(A)\det(D) = 0.
$$

Consider the other matrix

$$
M = \begin{bmatrix}
A & B \\
C & D
\end{bmatrix}
$$

such that $A$ is invertible.
One may take the first block row, pre-multiply by $-CA^{-1}$, and add it to the second block row.
Thus,

$$
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix}
=
\begin{bmatrix}
I & O \\
CA^{-1} & I
\end{bmatrix}
\begin{bmatrix}
A & B \\
O & D - CA^{-1}B
\end{bmatrix}.
$$

Therefore,

$$
\det(M) = \det(A)\det(D - CA^{-1}B).
$$

The matrix $D - CA^{-1}B$ is called the **Schur complement** of $A$ in $M$, denoted as $M / A$.
The notation is justified by $\det(M/A) = \det(M) / \det(A)$.

## Side stories

- Schur complement

## Experiments

##### Exercise 1

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False

while True:
    A = matrix(2, random_int_list(4,2))
    if A.det() != 0:
        break
B = matrix(2, random_int_list(6,3))
C = matrix(3, random_int_list(6,3))
D = matrix(3, random_int_list(9,3))

M = block_matrix([
    [A, B], 
    [C, D]
])

op = choice([1,2,3])
if op == 1:
    E = block_matrix([[zero_matrix(3,2), identity_matrix(3)], [identity_matrix(2), zero_matrix(2,3)]])
if op == 2:
    E = block_matrix([[A.inverse(), zero_matrix(2,3)], [zero_matrix(3,2), identity_matrix(3)]])
if op == 3:
    E = block_matrix([[identity_matrix(2), zero_matrix(2,3)], [-C*A.inverse(), identity_matrix(3)]])

W = E * M
if op == 1:
    W.subdivide(3,2)

print("M =")
pretty_print(M)

print("W =")
pretty_print(W)

if print_ans:
    print("E =")
    pretty_print(E)
    print("det(E) =", E.det())

##### Exercise 1(a)

觀察如何從 $M$ 經過區塊列運算得到 $W$，
並寫出相對應的區塊基本矩陣 $E$。

<!-- eng start -->
Find out how to obtain $W$ from $M$ by some block row operation. Then find the corresponding block elementary matrix $E$.
<!-- eng end -->

##### Exercise 1(b)

求 $\det(E)$。

<!-- eng start -->
Find $\det(E)$.
<!-- eng end -->

:::info
What do the experiments try to tell you? (open answer)

...
:::

## Exercises

##### Exercise 2

計算以下矩陣的行列式值。

<!-- eng start -->
Find the determinant of each of the following matrices.
<!-- eng end -->

##### Exercise 2(a)

$$
A = \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 2 \\
0 & 3 & 4
\end{bmatrix}.
$$

##### Exercise 2(b)

$$
A = \begin{bmatrix}
0 & 1 & 2 \\
1 & 0 & 0 \\
0 & 3 & 4
\end{bmatrix}.
$$

##### Exercise 2(c)

$$
A = \begin{bmatrix}
0 & 1 & 2 \\
0 & 3 & 4 \\
1 & 0 & 0
\end{bmatrix}.
$$

##### Exercise 2(d)

$$
A = \begin{bmatrix}
1 & 0 & 2 \\
3 & 0 & 4 \\
0 & 1 & 0
\end{bmatrix}.
$$

##### Exercise 3

計算以下矩陣的行列式值。

<!-- eng start -->
Find the determinant of each of the following matrices.
<!-- eng end -->

##### Exercise 3(a)

$$
A = \begin{bmatrix}
1 & 2 & 0 & 0 \\
3 & 4 & 0 & 0 \\
0 & 0 & 5 & 6 \\
0 & 0 & 7 & 8
\end{bmatrix}.
$$

##### Exercise 3(b)

$$
A = \begin{bmatrix}
0 & 0 & 5 & 6 \\
0 & 0 & 7 & 8 \\
1 & 2 & 0 & 0 \\
3 & 4 & 0 & 0
\end{bmatrix}.
$$

##### Exercise 3(c)

$$
A = \begin{bmatrix}
1 & 0 & 2 & 0 \\
0 & 5 & 0 & 6 \\
3 & 0 & 4 & 0 \\
0 & 7 & 0 & 8
\end{bmatrix}.
$$

##### Exercise 4

若矩陣 $A$ 可寫成

$$
A = \begin{bmatrix}
A_{11} & A_{12} & \cdots & A_{1n} \\
O & A_{22} & \ddots & \vdots \\
\vdots & \ddots & \ddots & A_{n-1,n} \\
O & \cdots & O & A_{nn}
\end{bmatrix}
$$

使得 $A_{11},\ldots,A_{nn}$ 皆是方陣
（可能不同大小），
說明 $\det(A) = \det(A_{11})\cdots \det(A_{nn})$。

<!-- eng start -->
Suppose $A$ can be written as

$$
A = \begin{bmatrix}
A_{11} & A_{12} & \cdots & A_{1n} \\
O & A_{22} & \ddots & \vdots \\
\vdots & \ddots & \ddots & A_{n-1,n} \\
O & \cdots & O & A_{nn}
\end{bmatrix}
$$

such that each of $A_{11},\ldots,A_{nn}$ are square matrices (probably of different sizes). Explain why $\det(A) = \det(A_{11})\cdots \det(A_{nn})$.
<!-- eng end -->

##### Exercise 5

若 $A$ 為 $m\times n$ 矩陣、
而 $B$ 為 $n\times m$ 矩陣，
證明

$$
\det\begin{bmatrix}
I_n & B \\
A & I_m
\end{bmatrix}
=
\det(I_m - AB)
=
\det(I_n - BA).
$$

<!-- eng start -->
Suppose $A$ is an $m\times n$ matrix while $B$ is an $n\times m$ matrix. Show that

$$
\det\begin{bmatrix}
I_n & B \\
A & I_m
\end{bmatrix}
=
\det(I_m - AB)
=
\det(I_n - BA).
$$
<!-- eng end -->