Macierz klatkowa

Macierz klatkowa – rozbiór macierzy na umieszczone obok siebie mniejsze macierze zwane klatkami. Macierz klatkowa powstaje po pogrupowaniu zarówno wierszy i kolumn tak, aby w każdej grupie były przylegające do siebie kolumny albo przylegające wiersze. Pojedynczą klatkę tworzą pola macierzy, dla których wszystkie wiersze należą do jednej grupy i wszystkie kolumny należą do jednej grupy.

Definicja formalna

Rozważmy macierze: $A=[a_{ij}]_{i=1,\dots ,n \atop j=1,\dots ,n},B=[b_{ij}]_{i=1,\dots ,m \atop j=1,\dots ,m},C=[c_{ij}]_{i=1,\dots ,n \atop j=1,\dots ,m},D=[d_{ij}]_{i=1,\dots ,m \atop j=1,\dots ,n}.$

Wówczas macierz $E=[e_{ij}]_{i=1,\dots ,n+m \atop j=1,\dots ,n+m}$ zdefiniowaną następująco:

e_{ij}:={\begin{cases}{\begin{matrix}a_{ij},&i\leqslant n,&j\leqslant n,\\b_{i-n\;j-n},&i>n,&j>n,\\c_{i\;j-n},&i\leqslant n,&j>n,\\d_{i-n\;j},&i>n,&j\leqslant n\end{matrix}}\end{cases}}

nazywamy macierzą klatkową. Macierz $E$ można zapisać w postaci

E:={\begin{bmatrix}A&C\\D&B\end{bmatrix}}.

Przykład

Macierz

P={\begin{bmatrix}1&1&2&2\\1&1&2&2\\3&3&4&4\\3&3&4&4\end{bmatrix}}

może zostać podzielona na 4 klatki 2×2

P_{11}={\begin{bmatrix}1&1\\1&1\end{bmatrix}},P_{12}={\begin{bmatrix}2&2\\2&2\end{bmatrix}},P_{21}={\begin{bmatrix}3&3\\3&3\end{bmatrix}},P_{22}={\begin{bmatrix}4&4\\4&4\end{bmatrix}}.

Podzieloną macierz możemy wówczas zapisać jako

P_{\mathrm {podzielone} }={\begin{bmatrix}P_{11}&P_{12}\\P_{21}&P_{22}\end{bmatrix}}.

Macierz klatkowo-diagonalna

Macierz klatkowo-diagonalna jest macierzą klatkową składającą się z kwadratowych macierzy na przekątnej i zawierającą wyłącznie zera w pozostałych polach. Macierz klatkowo-diagonalna $A$ ma postać

A={\begin{bmatrix}A_{1}&0&\ldots &0\\0&A_{2}&\ldots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\ldots &A_{n}\end{bmatrix}},

gdzie $A_{k}$ jest macierzą kwadratową.

Mnożenie macierzy klatkowych

Jeśli rozmiary klatek (ich liczby kolumn i wierszy) w dwóch macierzach klatkowych pasują do siebie, to

{\begin{bmatrix}A_{11}&A_{12}&\ldots &A_{1m}\\A_{21}&A_{22}&\ldots &A_{2m}\\\vdots &\vdots &\ddots &\vdots \\A_{n1}&A_{n2}&\ldots &A_{nm}\end{bmatrix}}\cdot {\begin{bmatrix}B_{11}&B_{12}&\ldots &B_{1k}\\B_{21}&B_{22}&\ldots &B_{2k}\\\vdots &\vdots &\ddots &\vdots \\B_{m1}&B_{m2}&\ldots &B_{mk}\end{bmatrix}}={\begin{bmatrix}C_{11}&C_{12}&\ldots &C_{1k}\\C_{21}&C_{22}&\ldots &C_{2k}\\\vdots &\vdots &\ddots &\vdots \\C_{n1}&C_{n2}&\ldots &C_{nk}\end{bmatrix}},

gdzie $C_{ij}=A_{i1}B_{1j}+A_{i2}B_{2j}+\ldots +A_{im}B_{mj}.$ Pozwala to na indukcyjne dowodzenie twierdzeń i konstruowanie algorytmów rekursywnych, np. algorytm Strassena.

Wyznacznik macierzy klatkowych

Niech $\mathbb {K}$ będzie ciałem.

Jeżeli macierz $A\in M_{n\times n}(\mathbb {K} ),B\in M_{m\times m}(\mathbb {K} ),D\in M_{m\times n}(\mathbb {K} )$ oraz $\Theta$ jest macierzą zerową typu $n\times m$ to:
$\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=\det(A)\det(B)$ (dowód w przypisach^[1]).

Jeżeli macierz $A\in M_{m\times n}(\mathbb {K} ),C\in M_{m\times m}(\mathbb {K} ),D\in M_{n\times n}(\mathbb {K} )$ oraz $\Theta$ jest macierzą zerową typu $n\times m,$ to:
$\det {\begin{bmatrix}A&C\\D&\Theta \end{bmatrix}}=(-1)^{mn}\det(C)\det(D).$

Przypisy

↑
Dowód indukcyjny (względem $m$ ) pierwszej własności wyznacznika macierzy klatkowej.
- Niech $n\in \mathbb {N} ,m=1.$ Wtedy
  $\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=\det {\begin{bmatrix}a_{11}&\dots &a_{1n}&0\\\vdots &\ddots &\vdots &\vdots \\a_{n1}&\dots &a_{nn}&0\\d_{11}&\dots &d_{1n}&b_{11}\end{bmatrix}}=b_{11}\det(A)=\det(B)\det(A).$
- Załóżmy, że teza zachodzi dla $n\in \mathbb {N} ,m=k-1.$
  Niech $A\in M_{n\times n}(\mathbb {K} ),B\in M_{k\times k}(\mathbb {K} ),D\in M_{k\times n}(\mathbb {K} ).$
  
  Wówczas z definicji wyznacznika macierzy otrzymuje się:
  $\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=\sum \limits _{i=1}^{k}~(-1)^{(n+k)+(n+i)}b_{ik}\det {\begin{bmatrix}A&\Theta \\D_{i}&B_{ik}\end{bmatrix}},$ gdzie $D_{i},$ to macierz powstała z macierzy $D$ poprzez wykreślenie i-tego wiersza, natomiast $B_{ik}$ z macierzy $B$ poprzez wykreślenie $i$ -tego wiersza oraz $k$ -tej kolumny.
  
  Ponieważ $B_{ik}\in M_{(k-1)\times (k-1)}(\mathbb {K} ),D_{i}\in M_{(k-1)\times n}(\mathbb {K} ),$ więc z założenia indukcyjnego:
  $\det {\begin{bmatrix}A&\Theta \\D_{i}&B_{ik}\end{bmatrix}}=\det(A)\det(B_{ik}).$
  
  Po podstawieniu:
  $\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=(-1)^{2n}\det(A)\sum \limits _{i=1}^{k}~(-1)^{k+i}b_{ik}\det(B_{ik})=\det(A)\det(B).$

Bibliografia

Andrzej Białynicki-Birula: Algebra liniowa z geometrią. Warszawa: Państwowe Wydawnictwo Naukowe, 1976.

[1] Dowód indukcyjny (względem $m$ ) pierwszej własności wyznacznika macierzy klatkowej.
Niech $n\in \mathbb {N} ,m=1.$ Wtedy
$\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=\det {\begin{bmatrix}a_{11}&\dots &a_{1n}&0\\\vdots &\ddots &\vdots &\vdots \\a_{n1}&\dots &a_{nn}&0\\d_{11}&\dots &d_{1n}&b_{11}\end{bmatrix}}=b_{11}\det(A)=\det(B)\det(A).$

Załóżmy, że teza zachodzi dla $n\in \mathbb {N} ,m=k-1.$
Niech $A\in M_{n\times n}(\mathbb {K} ),B\in M_{k\times k}(\mathbb {K} ),D\in M_{k\times n}(\mathbb {K} ).$

Wówczas z definicji wyznacznika macierzy otrzymuje się:
$\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=\sum \limits _{i=1}^{k}~(-1)^{(n+k)+(n+i)}b_{ik}\det {\begin{bmatrix}A&\Theta \\D_{i}&B_{ik}\end{bmatrix}},$ gdzie $D_{i},$ to macierz powstała z macierzy $D$ poprzez wykreślenie i-tego wiersza, natomiast $B_{ik}$ z macierzy $B$ poprzez wykreślenie $i$ -tego wiersza oraz $k$ -tej kolumny.

Ponieważ $B_{ik}\in M_{(k-1)\times (k-1)}(\mathbb {K} ),D_{i}\in M_{(k-1)\times n}(\mathbb {K} ),$ więc z założenia indukcyjnego:
$\det {\begin{bmatrix}A&\Theta \\D_{i}&B_{ik}\end{bmatrix}}=\det(A)\det(B_{ik}).$

Po podstawieniu:
$\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=(-1)^{2n}\det(A)\sum \limits _{i=1}^{k}~(-1)^{k+i}b_{ik}\det(B_{ik})=\det(A)\det(B).$

[2] Niech $n\in \mathbb {N} ,m=1.$ Wtedy
$\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=\det {\begin{bmatrix}a_{11}&\dots &a_{1n}&0\\\vdots &\ddots &\vdots &\vdots \\a_{n1}&\dots &a_{nn}&0\\d_{11}&\dots &d_{1n}&b_{11}\end{bmatrix}}=b_{11}\det(A)=\det(B)\det(A).$

[3] Załóżmy, że teza zachodzi dla $n\in \mathbb {N} ,m=k-1.$
Niech $A\in M_{n\times n}(\mathbb {K} ),B\in M_{k\times k}(\mathbb {K} ),D\in M_{k\times n}(\mathbb {K} ).$

Wówczas z definicji wyznacznika macierzy otrzymuje się:
$\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=\sum \limits _{i=1}^{k}~(-1)^{(n+k)+(n+i)}b_{ik}\det {\begin{bmatrix}A&\Theta \\D_{i}&B_{ik}\end{bmatrix}},$ gdzie $D_{i},$ to macierz powstała z macierzy $D$ poprzez wykreślenie i-tego wiersza, natomiast $B_{ik}$ z macierzy $B$ poprzez wykreślenie $i$ -tego wiersza oraz $k$ -tej kolumny.

Ponieważ $B_{ik}\in M_{(k-1)\times (k-1)}(\mathbb {K} ),D_{i}\in M_{(k-1)\times n}(\mathbb {K} ),$ więc z założenia indukcyjnego:
$\det {\begin{bmatrix}A&\Theta \\D_{i}&B_{ik}\end{bmatrix}}=\det(A)\det(B_{ik}).$

Po podstawieniu:
$\det {\begin{bmatrix}A&\Theta \\D&B\end{bmatrix}}=(-1)^{2n}\det(A)\sum \limits _{i=1}^{k}~(-1)^{k+i}b_{ik}\det(B_{ik})=\det(A)\det(B).$

[1]