Macierz klatkowa

Z Wikipedii

Macierzą klatkową w algebrze liniowej nazywamy 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.

[edytuj] 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}.$

[edytuj] 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 posiada postać

$\mathbf{A} = \begin{bmatrix} A_{1} & 0 & \cdots & 0 \\ 0 & A_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & A_{n} \end{bmatrix}$

gdzie A_k jest macierzą kwadratową.

[edytuj] Działania na macierzach klatkowych

Znaczenie macierzy klatkowych wynika z tego, że jeśli rozmiary klatek (ich liczby kolumn i wierszy) pasują do siebie, to

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

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