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_{i j}]_{\binom{i = 1, \dots, n}{j = 1, \dots, n}}, B = [b_{i j}]_{\binom{i = 1, \dots, m}{j = 1, \dots, m}}, C = [c_{i j}]_{\binom{i = 1, \dots, n}{j = 1, \dots, m}}, D = [d_{i j}]_{\binom{i = 1, \dots, m}{j = 1, \dots, n}} .$

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

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

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

E : = [\begin{matrix} A & C \\ D & B \end{matrix}] .

Przykład

Macierz

P = [\begin{matrix} 1 & 1 & 2 & 2 \\ 1 & 1 & 2 & 2 \\ 3 & 3 & 4 & 4 \\ 3 & 3 & 4 & 4 \end{matrix}]

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

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

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

P_{p o d z i e l o n e} = [\begin{matrix} P_{11} & P_{12} \\ P_{21} & P_{22} \end{matrix}] .

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{matrix} A_{1} & 0 & \dots & 0 \\ 0 & A_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & A_{n} \end{matrix}],

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{matrix} A_{11} & A_{12} & \dots & A_{1 m} \\ A_{21} & A_{22} & \dots & A_{2 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ A_{n 1} & A_{n 2} & \dots & A_{n m} \end{matrix}] \cdot [\begin{matrix} B_{11} & B_{12} & \dots & B_{1 k} \\ B_{21} & B_{22} & \dots & B_{2 k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ B_{m 1} & B_{m 2} & \dots & B_{m k} \end{matrix}] = [\begin{matrix} C_{11} & C_{12} & \dots & C_{1 k} \\ C_{21} & C_{22} & \dots & C_{2 k} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ C_{n 1} & C_{n 2} & \dots & C_{n k} \end{matrix}],

gdzie $C_{i j} = A_{i 1} B_{1 j} + A_{i 2} B_{2 j} + \dots + A_{i m} B_{m j} .$ Pozwala to na indukcyjne dowodzenie twierdzeń i konstruowanie algorytmów rekursywnych, np. algorytm Strassena.

Wyznacznik macierzy klatkowych

Niech $𝕂$ będzie ciałem.

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

Jeżeli macierz $A \in M_{m \times n} (𝕂), C \in M_{m \times m} (𝕂), D \in M_{n \times n} (𝕂)$ oraz $Θ$ jest macierzą zerową typu $n \times m,$ to:
$\det [\begin{matrix} A & C \\ D & Θ \end{matrix}] = (- 1)^{m n} \det (C) \det (D) .$

Przypisy

Szablon:Przypisy

Bibliografia

Szablon:Cytuj książkę

Szablon:Macierz

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

[1] Dowód indukcyjny (względem $m$ ) pierwszej własności wyznacznika macierzy klatkowej.
Niech $n \in ℕ, m = 1 .$ Wtedy
$\det [\begin{matrix} A & Θ \\ D & B \end{matrix}] = \det [\begin{matrix} a_{11} & \dots & a_{1 n} & 0 \\ ⋮ & ⋱ & ⋮ & ⋮ \\ a_{n 1} & \dots & a_{n n} & 0 \\ d_{11} & \dots & d_{1 n} & b_{11} \end{matrix}] = b_{11} \det (A) = \det (B) \det (A) .$

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

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

Ponieważ $B_{i k} \in M_{(k - 1) \times (k - 1)} (𝕂), D_{i} \in M_{(k - 1) \times n} (𝕂),$ więc z założenia indukcyjnego:
$\det [\begin{matrix} A & Θ \\ D_{i} & B_{i k} \end{matrix}] = \det (A) \det (B_{i k}) .$

Po podstawieniu:
$\det [\begin{matrix} A & Θ \\ D & B \end{matrix}] = (- 1)^{2 n} \det (A) \sum_{i = 1}^{k} (- 1)^{k + i} b_{i k} \det (B_{i k}) = \det (A) \det (B) .$

[2] Niech $n \in ℕ, m = 1 .$ Wtedy
$\det [\begin{matrix} A & Θ \\ D & B \end{matrix}] = \det [\begin{matrix} a_{11} & \dots & a_{1 n} & 0 \\ ⋮ & ⋱ & ⋮ & ⋮ \\ a_{n 1} & \dots & a_{n n} & 0 \\ d_{11} & \dots & d_{1 n} & b_{11} \end{matrix}] = b_{11} \det (A) = \det (B) \det (A) .$

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

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

Ponieważ $B_{i k} \in M_{(k - 1) \times (k - 1)} (𝕂), D_{i} \in M_{(k - 1) \times n} (𝕂),$ więc z założenia indukcyjnego:
$\det [\begin{matrix} A & Θ \\ D_{i} & B_{i k} \end{matrix}] = \det (A) \det (B_{i k}) .$

Po podstawieniu:
$\det [\begin{matrix} A & Θ \\ D & B \end{matrix}] = (- 1)^{2 n} \det (A) \sum_{i = 1}^{k} (- 1)^{k + i} b_{i k} \det (B_{i k}) = \det (A) \det (B) .$

[1]

Macierz klatkowa

Spis treści

Definicja formalna

Przykład

Macierz klatkowo-diagonalna

Mnożenie macierzy klatkowych

Wyznacznik macierzy klatkowych

Przypisy

Bibliografia

Menu nawigacyjne

Macierz klatkowa

Definicja formalna

Przykład

Macierz klatkowo-diagonalna

Mnożenie macierzy klatkowych

Wyznacznik macierzy klatkowych

Przypisy

Bibliografia

Menu nawigacyjne

Szukaj