Lineaire Algebra – Symmetrische matrices en kwadratische vormen – De singuliere-waardendecompositie

Niet elke (vierkante) matrix is diagonaliseerbaar. We kunnen dus niet elke matrix \(A\) schrijven als \(A=PDP^{-1}\) met \(P\) een inverteerbare matrix en \(D\) een diagonaalmatrix. Maar symmetrische matrices zijn zelfs orthogonaal diagonaliseerbaar. Dat wil zeggen dat elke symmetrische matrix \(A\) geschreven kan worden als \(A=PDP^T\) voor zekere orthogonale matrix \(P\) en diagonaalmatrix \(D\). Die (orthogonale) diagonaliseerbaarheid heeft vele voordelen en toepassingen.

Het is wel mogelijk om elke (eventueel niet-vierkante) matrix \(A\) te schrijven als \(A=U\Sigma V^T\) voor zekere orthogonale matrices \(U\) en \(V\) en een matrix \(\Sigma\) met dezelfde afmetingen als \(A\) die veel op een diagonaalmatrix lijkt. Dit noemt men een singuliere-waardendecompositie van de matrix \(A\).

Als \(A\) een symmetrische matrix is, dan geldt voor elke \(\mathbf{x}\) met \(A\mathbf{x}=\lambda\mathbf{x}\) en \(||\mathbf{x}||=1\) dat

\[||A\mathbf{x}||=||\lambda\mathbf{x}||=|\lambda|\,||\mathbf{x}||=|\lambda|.\]

Zo'n vector \(\mathbf{x}\) wordt door de lineaire afbeelding \(\mathbf{x}\mapsto A\mathbf{x}\) afgebeeld op een vector met lengte \(|\lambda|\). Die absolute waarde van de eigenwaarde \(\lambda\) is dus een maat voor de oprekking of inkrimping door de lineaire afbeelding \(\mathbf{x}\mapsto A\mathbf{x}\) die bij de matrix \(A\) hoort.

Dit principe kan ook bij niet-vierkante matrices worden onderzocht. Als \(A\) een willekeurige \(m\times n\) matrix is, dan is \(\mathbf{x}\mapsto A\mathbf{x}\) een lineaire afbeelding van \(\mathbb{R}^n\) naar \(\mathbb{R}^m\). We kijken vervolgens naar de verzameling \(\{\mathbf{x}\in\mathbb{R}^n\,:\,||\mathbf{x}||=1\}\) in \(\mathbb{R}^n\) en onderzoeken de mogelijke waarden van \(||A\mathbf{x}||\). Nu geldt:

\[||A\mathbf{x}||^2=(A\mathbf{x})\cdot(A\mathbf{x})=(A\mathbf{x})^T(A\mathbf{x})=\mathbf{x}^TA^TA\mathbf{x}.\]

Dit is een kwadratische vorm waarvan de matrix gelijk is aan \(A^TA\). Deze matrix is symmetrisch, want: \((A^TA)^T=A^T(A^T)^T=A^TA\). We zoeken vervolgens het maximum en het minimum van deze kwadratische vorm onder de voorwaarde dat \(||\mathbf{x}||=1\). Dat is dus respectievelijk de grootste en de kleinste eigenwaarde van de symmetrische matrix \(A^TA\).

Voorbeeld: Zie: Lay, §7.4. De matrix \(A=\begin{pmatrix}4&11&14\\8&7&-2\end{pmatrix}\) bepaalt een lineaire afbeelding \(\mathbf{x}\mapsto A\mathbf{x}\) van \(\mathbb{R}^3\) naar \(\mathbb{R}^2\). In \(\mathbb{R}^3\) beperken we ons tot de eenheidsbol \(\{\mathbf{x}\in\mathbb{R}^3\,:\,||\mathbf{x}||=1\}\). De matrix \(A^TA\) heeft de eigenwaarden \(\lambda_1=360\), \(\lambda_2=90\) en \(\lambda_3=0\). De bijbehorende orthonormale eigenvectoren zijn:

\[\mathbf{v}_1=\pm\frac{1}{3}\begin{pmatrix}1\\2\\2\end{pmatrix},\quad\mathbf{v}_2=\pm\frac{1}{3}\begin{pmatrix}2\\1\\-2\end{pmatrix} \quad\text{en}\quad\mathbf{v}_3=\pm\frac{1}{3}\begin{pmatrix}2\\-2\\1\end{pmatrix}.\]

Het maximum van \(||A\mathbf{x}||\) onder de voorwaarde dat \(||\mathbf{x}||=1\) is dus \(\sqrt{360}=6\sqrt{10}\). Dit maximum wordt aangenomen als \(\mathbf{x}=\mathbf{v}_1\):

\[A\mathbf{v}_1=\pm\frac{1}{3}\begin{pmatrix}4&11&14\\8&7&-2\end{pmatrix}\begin{pmatrix}1\\2\\2\end{pmatrix} =\pm\frac{1}{3}\begin{pmatrix}4+22+28\\8+14-4\end{pmatrix}=\pm\frac{1}{3}\begin{pmatrix}54\\18\end{pmatrix} =\pm\begin{pmatrix}18\\6\end{pmatrix}.\]

Het maximum van \(||A\mathbf{x}||\) onder de voorwaarden dat \(||\mathbf{x}||=1\) en \(\mathbf{x}^T\mathbf{v}_1\) is dus \(\sqrt{90}=3\sqrt{10}\). Dit maximum wordt aangenomen als \(\mathbf{x}=\mathbf{v}_2\):

\[A\mathbf{v}_2=\pm\frac{1}{3}\begin{pmatrix}4&11&14\\8&7&-2\end{pmatrix}\begin{pmatrix}2\\1\\-2\end{pmatrix} =\pm\frac{1}{3}\begin{pmatrix}8+11-28\\16+7+4\end{pmatrix}=\pm\frac{1}{3}\begin{pmatrix}-9\\27\end{pmatrix} =\pm\begin{pmatrix}-3\\9\end{pmatrix}.\]

De verzameling \(\{A\mathbf{x}\,:\,||\mathbf{x}||=1\}\) blijkt nu een ellips (het binnengebied plus de rand) te zijn met halve assen \(\pm\begin{pmatrix}18\\6\end{pmatrix}\) en \(\pm\begin{pmatrix}-3\\9\end{pmatrix}\). De lengtes van die halve assen zijn respectievelijk \(6\sqrt{10}\) en \(3\sqrt{10}\):

\[||\pm\begin{pmatrix}18\\6\end{pmatrix}||=6||\begin{pmatrix}3\\1\end{pmatrix}||=6\sqrt{10}\quad\text{en}\quad ||\pm\begin{pmatrix}-3\\9\end{pmatrix}||=3||\begin{pmatrix}-1\\3\end{pmatrix}||=3\sqrt{10}.\]

Als \(A\) een willekeurige \(m\times n\) matrix is, dan is \(A^TA\) een symmetrische \(n\times n\) matrix. Deze matrix is dus orthogonaal diagonaliseerbaar, dat wil zeggen: er bestaat een orthonormale basis \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) van \(\mathbb{R}^n\) bestaande uit eigenvectoren van \(A^TA\). Stel dat \(A^TA\mathbf{v}_k=\lambda_k\mathbf{v}_k\) voor \(k=1,2,\ldots,n\), dan geldt:

\[||A\mathbf{v}_k||^2=(A\mathbf{v}_k)^T(A\mathbf{v}_k)=\mathbf{v}_k^TA^TA\mathbf{v}_k=\mathbf{v}_k^T(\lambda_k\mathbf{v}_k) =\lambda_k(\mathbf{v}_k^T\mathbf{v}_k)=\lambda_k,\quad k=1,2,\ldots,n.\]

Hieruit volgt dat alle eigenwaarden van \(A^TA\) niet-negatief zijn. We kunnen die eigenwaarden dus als volgt rangschikken: \(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n\geq0\).

De singuliere waarden van \(A\) zijn de wortels van de eigenwaarden van \(A^TA\). Dit zijn dus de lengtes van de vectoren \(A\mathbf{v}_k\) met \(k=1,2,\ldots,n\):

\[\sigma_k:=\sqrt{\lambda_k}=||A\mathbf{v}_k||,\quad k=1,2,\ldots,n.\]

Stelling: Stel dat \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) een orthonormale basis van \(\mathbb{R}^n\) is, bestaande uit eigenvectoren van \(A^TA\) behorende bij de eigenwaarden \(\lambda_1,\ldots,\lambda_n\) zodat \(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n\geq0\). Als \(A\) \(r\) positieve singuliere waarden heeft, dan is \(\{A\mathbf{v}_1,\ldots,A\mathbf{v}_r\}\) een orthogonale basis van \(\text{Col}(A)\) en geldt dat \(\text{rank}(A)=r\).

Bewijs: Omdat \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) een orthogonale verzameling is, volgt dat

\[(A\mathbf{v}_i)\cdot(A\mathbf{v}_j)=(A\mathbf{v}_i)^T(A\mathbf{v}_j)=\mathbf{v}_i^TA^TA\mathbf{v}_j =\mathbf{v}_i^T(\lambda_j\mathbf{v}_j)=\lambda_j(\mathbf{v}_i\cdot\mathbf{v}_j)=0,\quad i\neq j.\]

Dus: \(\{A\mathbf{v}_1,\ldots,A\mathbf{v}_n\}\) is ook een orthogonale verzameling.

De singuliere waarden van \(A\) zijn de lengtes van de vectoren \(A\mathbf{v}_1,\ldots,A\mathbf{v}_n\). Omdat \(A\) \(r\) positieve singuliere waarden heeft, en dus \(n-r\) singuliere waarden gelijk aan nul, volgt dat \(A\mathbf{v}_k\neq\mathbf{0}\) voor \(k=1,2,\ldots,r\) en \(A\mathbf{v}_k=\mathbf{0}\) voor \(k=r+1,r+2,\ldots,n\). Dus: \(\{A\mathbf{v}_1,\ldots,A\mathbf{v}_r\}\) is een lineair onafhankelijke verzameling vectoren in \(\text{Col}(A)\). Verder geldt dat iedere vector \(\mathbf{y}\in\text{Col}(A)\) geschreven kan worden als \(\mathbf{y}=A\mathbf{x}\) voor zekere \(\mathbf{x}\in\mathbb{R}^n\). Nu is \(\mathbf{x}=c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n\) voor zekere \(c_1,\ldots,c_n\in\mathbb{R}\), want \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) is een basis van \(\mathbb{R}^n\). Dus:

\[\mathbf{y}=A\mathbf{x}=A(c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n)=c_1A\mathbf{v}_1+\cdots+c_rA\mathbf{v}_r.\]

Dus: \(\text{Col}(A)=\text{Span}\{A\mathbf{v}_1,\ldots,A\mathbf{v}_r\}\) en \(\{A\mathbf{v}_1,\ldots,A\mathbf{v}_r\}\) is een orthogonale basis van \(\text{Col}(A)\). Dus: \(\text{rank}(A)=\dim(\text{Col}(A))=r\).

Stelling: Stel dat \(A\) een \(m\times n\) matrix is met \(\text{rank}(A)=r\). Dan bestaat er een orthogonale \(m\times m\) matrix \(U\), een orthogonale \(n\times n\) matrix \(V\) en een \(m\times n\) matrix \(\Sigma\) waarvan de eerste \(r\) diagonaalelementen gelijk zijn aan de singuliere waarden \(\sigma_1,\ldots,\sigma_r\) van \(A\) met \(\sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r>0\) en alle andere elementen gelijk aan nul, zodat \(A=U\Sigma V^T\).

Elke factorisatie van de vorm \(A=U\Sigma V^T\) met \(U\) en \(V\) orthogonale matrices, noemt men een singuliere-waardendecompositie van de matrix \(A\). Zo'n ontbinding is niet uniek. Het bewijs is constructief:

Bewijs: Stel dat \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) een orthogonale basis van \(\mathbb{R}^n\) is, bestaande uit eigenvectoren van de matrix \(A^TA\) behorende bij de eigenwaarden \(\lambda_1,\ldots,\lambda_n\) respectievelijk met \(\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_n\geq0\). Omdat \(\text{rank}(A)=r\) is dan \(\{A\mathbf{v}_1,\ldots,A\mathbf{v}_r\}\) een orthogonale basis van \(\text{Col}(A)\). De lengtes van de vectoren \(A\mathbf{v}_1,\ldots,A\mathbf{v}_r\) zijn de eerste \(r\) (positieve) singuliere waarden van \(A\), dus:

\[A\mathbf{v}_k=\sigma_k\mathbf{u}_k,\quad k=1,2,\ldots,r,\]

waarbij \(\{\mathbf{u}_1,\ldots,\mathbf{u}_r\}\) een orthonormale verzameling in \(\mathbb{R}^m\) is. Deze verzameling kan eventueel worden uitgebreid tot een orthonormale basis \(\{\mathbf{u}_1,\ldots,\mathbf{u}_m\}\) van \(\mathbb{R}^m\) door geschikte eenheidsvectoren \(\mathbf{u}_{r+1},\ldots,\mathbf{u}_m\) toe te voegen. Definieer nu de matrices

\[U=\Bigg(\mathbf{u}_1\;\ldots\;\mathbf{u}_m\Bigg)\quad\text{en}\quad V=\Bigg(\mathbf{v}_1\;\ldots\;\mathbf{v}_n\Bigg).\]

Dan is \(U\) een orthogonale \(m\times m\) matrix en \(V\) een orthogonale \(n\times n\) matrix. Verder geldt:

\[AV=A\Bigg(\mathbf{v}_1\;\ldots\;\mathbf{v}_n\Bigg)=\Bigg(A\mathbf{v}_1\;\ldots\;A\mathbf{v}_r\;\mathbf{0}\;\ldots\;\mathbf{0}\Bigg)\]

en

\[U\Sigma=\Bigg(\mathbf{u}_1\;\ldots\;\mathbf{u}_m\Bigg)\begin{pmatrix}\sigma_1&&0&\ldots&0\\&\ddots&\vdots&&\vdots\\ 0&&\sigma_r&0&\ldots&0\\0&\ldots&0&0&\ldots&0\\\vdots&&\vdots&\vdots&\ddots&\vdots\\0&\ldots&0&0&\ldots&0\end{pmatrix} =\Bigg(\sigma_1\mathbf{u}_1\;\ldots\;\sigma_r\mathbf{u}_r\;\mathbf{0}\;\ldots\;\mathbf{0}\Bigg).\]

Hieruit volgt dat \(AV=U\Sigma\) en omdat \(V\) een orthogonale matrix is en dus \(V^{-1}=V^T\) volgt: \(A=U\Sigma V^{-1}=U\Sigma V^T\).

Voorbeeld: Voor de matrix \(A=\begin{pmatrix}4&11&14\\8&7&-2\end{pmatrix}\) uit het eerste voorbeeld kiezen we bijvoorbeeld:

\[\mathbf{v}_1=\frac{1}{3}\begin{pmatrix}1\\2\\2\end{pmatrix},\quad\mathbf{v}_2=\frac{1}{3}\begin{pmatrix}2\\1\\-2\end{pmatrix} \quad\text{en}\quad\mathbf{v}_3=\frac{1}{3}\begin{pmatrix}2\\-2\\1\end{pmatrix}.\]

Dan volgt:

\[A\mathbf{v}_1=\begin{pmatrix}18\\6\end{pmatrix}=6\sqrt{10}\cdot\frac{1}{\sqrt{10}}\begin{pmatrix}3\\1\end{pmatrix} =\sigma_1\mathbf{u}_1\quad\Longrightarrow\quad\mathbf{u}_1=\frac{1}{\sqrt{10}}\begin{pmatrix}3\\1\end{pmatrix}\]

en

\[A\mathbf{v}_2=\begin{pmatrix}-3\\9\end{pmatrix}=3\sqrt{10}\cdot\frac{1}{\sqrt{10}}\begin{pmatrix}1\\-3\end{pmatrix} =\sigma_2\mathbf{u}_2\quad\Longrightarrow\quad\mathbf{u}_2=\frac{1}{\sqrt{10}}\begin{pmatrix}1\\-3\end{pmatrix}.\]

Dan volgt dat \(A=U\Sigma V^T\) met

\[U=\frac{1}{\sqrt{10}}\begin{pmatrix}3&1\\1&-3\end{pmatrix},\quad\Sigma=\begin{pmatrix}6\sqrt{10}&0&0\\0&3\sqrt{10}&0\end{pmatrix} \quad\text{en}\quad V=\frac{1}{3}\begin{pmatrix}1&2&2\\2&1&-2\\2&-2&1\end{pmatrix}.\]

Merk op dat \(\{\mathbf{u}_1,\mathbf{u}_2\}\) al een basis van \(\mathbb{R}^2\) is. Deze hoeft dus niet verder te worden aangevuld.

Als \(A=U\Sigma V^T\) een singuliere-waardendecompositie van \(A\) is, dan is \(A^T=(U\Sigma V^T)^T=V\Sigma U^T\) een singuliere-waardendecompositie van \(A^T\). In bovenstaand voorbeeld is \(A^TA\) een \(3\times3\) matrix, terwijl \(AA^T\) een (2\times 2\) matrix is. Het is daarom iets eenvoudiger om de singuliere waarden uit de eigenwaarden van \(A^T\) te bepalen. Dat zijn er dan twee: \(\sigma_1=6\sqrt{10}\) en \(\sigma_2=3\sqrt{10}\). De rollen van de matrices \(U\) en \(V\) worden dan omgedraaid, waarbij er slechts twee kolommen worden gevonden voor de orthogonale \(3\times 3\) matrix. De derde kolom moet dan nog worden geconstrueerd. Dit zien we ook in het volgende voorbeeld.

Voorbeeld: Als \(A=\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix}\), dan is \(A^TA=\begin{pmatrix}2&1\\1&2\end{pmatrix}\) met eigenwaarden \(\lambda_1=3\) en \(\lambda_2=1\). Dus: \(\sigma_1=\sqrt{3}\) en \(\sigma_2=1\). Verder vinden we eenvoudig dat \(\mathbf{v}_1=\dfrac{1}{\sqrt{2}}\begin{pmatrix}1\\1\end{pmatrix}\) en \(\mathbf{v}_2=\dfrac{1}{\sqrt{2}}\begin{pmatrix}1\\-1\end{pmatrix}\) twee orthonormale eigenvectoren van \(A^TA\) zijn behorende bij de eigenwaarden \(\lambda_1=3\) en \(\lambda_2=1\) respectievelijk. Vervolgens vinden we:

\[A\mathbf{v}_1=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix}\begin{pmatrix}1\\1\end{pmatrix} =\frac{1}{\sqrt{2}}\begin{pmatrix}2\\1\\1\end{pmatrix}=\sqrt{3}\cdot\frac{1}{\sqrt{6}}\begin{pmatrix}2\\1\\1\end{pmatrix} =\sigma_1\mathbf{u}_1\quad\Longrightarrow\quad\mathbf{u}_1=\frac{1}{\sqrt{6}}\begin{pmatrix}2\\1\\1\end{pmatrix}\]

en

\[A\mathbf{v}_2=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix}\begin{pmatrix}1\\-1\end{pmatrix} =\frac{1}{\sqrt{2}}\begin{pmatrix}0\\-1\\1\end{pmatrix}=1\cdot\frac{1}{\sqrt{2}}\begin{pmatrix}0\\-1\\1\end{pmatrix} =\sigma_2\mathbf{u}_2\quad\Longrightarrow\quad\mathbf{u}_2=\frac{1}{\sqrt{2}}\begin{pmatrix}0\\-1\\1\end{pmatrix}.\]

We vinden nu dus dat \(A=U\Sigma V^T\) met

\[U=\begin{pmatrix}2/\sqrt{6}&0&.\;\\2/\sqrt{6}&-1/\sqrt{2}&.\;\\1/\sqrt{6}&1/\sqrt{2}&.\;\end{pmatrix},\quad\Sigma =\begin{pmatrix}\sqrt{3}&0\\0&1\\0&0\end{pmatrix}\quad\text{en}\quad V=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.\]

De derde kolom van \(U\) is nu eigenlijk willekeurig, maar we willen wel dat \(U\) een orthogonale matrix is. We moeten de derde kolom daarom zo kiezen dat deze lengte \(1\) heeft en orthogonaal is ten opzichte van de eerste twee kolommen. Stel dat die derde kolom gelijk is aan \(\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}\), dan volgt dat \(2x_1+x_2+x_3=0\) en \(-x_2+x_3=0\). Hieruit volgt dat \(-x_1=x_2=x_3\). Omdat de lengte \(1\) moet zijn, kiezen we bijvoorbeeld \(\dfrac{1}{\sqrt{3}}\begin{pmatrix}-1\\1\\1\end{pmatrix}\). Voor de matrix \(U\) vinden we dan:

\[U=\begin{pmatrix}2/\sqrt{6}&0&-1/\sqrt{3}\\2/\sqrt{6}&-1/\sqrt{2}&1/\sqrt{3}\\1/\sqrt{6}&1/\sqrt{2}&1/\sqrt{3}\end{pmatrix} =\frac{1}{\sqrt{6}}\begin{pmatrix}2&0&-\sqrt{2}\\1&-\sqrt{3}&\sqrt{2}\\1&\sqrt{3}&\sqrt{2}\end{pmatrix}.\]

---

Laatst gewijzigd op 5 mei 2021