CR-Zerlegung

Die CR Zerlegung ist für Matrizen das, was die Primfaktorzerlegung für Natürliche Zahlen ist.

Bsp. $1001=7\cdot 11\cdot 13$

Für Matrizen heisst das: Schreibe $A$ als Produkt anderer Matrizen, um $A$ besser zu verstehen.

Theorem 2.46

Sei $A$ eine $m\times n$ Matrix mit Rang $r$ (Definition 2.10)
Sei $C$ die $m\times r$ Submatrix mit den unabhängigen Spalten von $A$.

Dann gibt es genau eine eindeutige $r\times n$ Matrix $R^{\prime }$ mit $A=C{R}^{\prime }$

Beispiel ($r=1$):

$$\left[\begin{array}{ccc}2& 4& 6\\ 3& 6& 9\end{array}\right]=\underset{C:2\times 1}{\underbrace{\left[\begin{array}{c}2\\ 3\end{array}\right]}}\cdot \underset{R^{\prime }:1\times 3}{\underbrace{\left[\begin{array}{ccc}1& 2& 3\end{array}\right]}}$$

Die Spalten von $R^{\prime }$ sind die Skalare, um jede Spalte von $A$ als skalares Vielfaches der ersten Spalte zu schreiben.

Beweis

$A$ und $C$ haben den gleichen Spaltenraum (Lemma 2.11) $⟹$ jede Spalte von $A$ ist Linearkombination von $C$:

$$\underset{\text{Spalte von }A}{\underbrace{v_j}}=C\cdot \underset{\text{Vektor von r Skalaren}}{\underbrace{x_j}}$$

Als Matrizen:

$$\underset{A}{\underbrace{\left[\begin{array}{cccc}|& |& & |\\ {\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\\ |& |& & |\end{array}\right]}}=C\cdot \underset{R^{\prime },r\times n}{\underbrace{\left[\begin{array}{cccc}|& |& & |\\ {\mathbf{x}}_1& {\mathbf{x}}_2& \cdots & {\mathbf{x}}_n\\ |& |& & |\end{array}\right]}}$$

Die Spalten von $C$ sind linear unabhängig, d.h. alle $x_j$ sind eindeutig (Lemma 1.24) Also ist $R^{\prime }$ eindeutig.

Link to original

$A=C{R}^{\prime }$ und Matrixkompression

$m\times n$ Matrix $A$ hat $m\cdot n$ Einträge
$m\times n$ Matrix $A$ mit Rang r hat $m\cdot n$ Einträge

$C$ hat $m\cdot r$ Einträge
$R^{\prime }$ hat $r\cdot n$ Einträge
Heisst zusammen gibt es $(m+n)\cdot r$ Einträge

Wenn $r$ klein ist, dann ist die Übertragung von $C$ und $R^{\prime }$ anstatt $A$ viel effizienter.
Wenn z.B. $m=n=1000$ und $r=10$ ist, dann müssen für die Übertragung der $m\times n$ Matrix $A$ $1^{\prime }000^{\prime }000$ Einträge übertragen werden.
Wenn man die beiden Matrizen $C$ und $R^{\prime }$ verwendet, muss man nur $(m+n)\cdot r$ Einträge übertragen. In diesem Fall $20^{\prime }000$. Die Anzahl der Einträge, welche übertragen werden schrumpft also von $1^{\prime }000^{\prime }000$ auf $20^{\prime }000$ Einträge.

Beispiel der CR Zerlegung

Die folgende Matrix $A$ soll zerlegt werden:

$$A=\left[\begin{array}{ccc}1& 2& 3\\ 2& 4& 6\\ 1& 1& 2\end{array}\right]$$

Der Rang von $A$ beträgt 2, die ersten beiden Spalten sind unabhängig, die dritte kann hingegen als Linearkombination der ersten beiden geschrieben werden.

$$\underset{a_3}{\underbrace{\left(\begin{array}{c}3\\ 6\\ 2\end{array}\right)}}=\underset{a_1}{\underbrace{\left(\begin{array}{c}1\\ 2\\ 1\end{array}\right)}}+\underset{a_2}{\underbrace{\left(\begin{array}{c}2\\ 4\\ 1\end{array}\right)}}$$

Die Matrix $C$ ist also:

$$C=\left[\begin{array}{cc}1& 2\\ 2& 4\\ 1& 1\end{array}\right]$$

Die Matrix $R$ ist die folgende:

$$R=\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\end{array}\right]$$

Wie man die Matrix $R$ effizient bestimmen kann ist in 23.10.2026 - Woche 6 erläutert.

Die Matrix $R$ sagt nun, wie man auf die Spalten von $A$ kommt. Das

$$\left[\begin{array}{c}1\\ 0\end{array}\right]$$

in der ersten Spalte sagt, dass man die erste Spalte von $C$ einmal verwenden muss, um die erste Spalte von $A$ zu erhalten. In der zweiten Zeile ist eine $0$. Die zweite Spalte von $C$ benötigt man also null Mal. Analog dazu auch die zweite Spalte, hier ist der Eintrag in $R$

$$\left[\begin{array}{c}0\\ 1\end{array}\right]$$

Also einmal die zweite Spalte und null mal die erste Spalte.

Interessant wird es bei der dritten Spalte, diese ist linear abhängig von den ersten beiden Spalten.

$$\left[\begin{array}{c}1\\ 1\end{array}\right]$$

Sagt also aus, dass man einmal die erste Spalte nehmen muss und dazu einmal die zweite Spalte addieren muss. Tatsächlich stimmt das auch mit der Rechnung von oben

$$\left(\begin{array}{c}3\\ 6\\ 2\end{array}\right)=\left(\begin{array}{c}1\\ 2\\ 1\end{array}\right)+\left(\begin{array}{c}2\\ 4\\ 1\end{array}\right)$$

überein. Es gilt also:

$$\left[\begin{array}{cc}1& 2\\ 2& 4\\ 1& 1\end{array}\right]\left[\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\end{array}\right]=\left[\begin{array}{ccc}1& 2& 3\\ 2& 4& 6\\ 1& 1& 2\end{array}\right]$$