Linear Algebra – Symmetric matrices and quadratic forms – Constrained optimization

We look for maximal and minimal values of a quadratic form \(Q(\mathbf{x})\) on \(\mathbb{R}^n\) under certain conditions. Such a condition is for instance that \(\mathbf{x}\in\mathbb{R}^n\) is a unit vector, that is:

\[||\mathbf{x}||=1\quad\Longleftrightarrow\quad||\mathbf{x}||^2=1\quad\Longleftrightarrow\quad\mathbf{x}^T\mathbf{x}= \quad\Longleftrightarrow\quad x_1^2+\cdots+x_n^2=1.\]

Example: Suppose that \(Q:\mathbb{R}^3\to\mathbb{R}\) with \(Q(\mathbf{x})=7x_1^2+4x_2^2+2x_3^2\). Then what is the maximal and minimal value of \(Q(\mathbf{x})\) provided that \(\mathbf{x}^T\mathbf{a}=1\) or equivalently \(x_1^2+x_2^2+x_3^2=1\). Note that

\[Q(\mathbf{x})=7x_1^2+4x_2^2+2x_3^2\leq 7x_1^2+7x_2^2+7x_3^2=7(x_1^2+x_2^2+x_3^2)=7\]

and

\[Q(\mathbf{x})=7x_1^2+4x_2^2+2x_3^2\geq 2x_1^2+2x_2^2+7x_3^2=2(x_1^2+x_2^2+x_3^2)=2.\]

Further we have: \(\mathbf{x}=\begin{pmatrix}1\\0\\0\end{pmatrix}\;\Longrightarrow\;Q(\mathbf{x})=7\) and \(\mathbf{x}=\begin{pmatrix}0\\0\\1\end{pmatrix}\;\Longrightarrow\;Q(\mathbf{x})=2\).

This implies that the maximal value of \(Q(\mathbf{x})\) subject to the constraint \(\mathbf{x}^T\mathbf{x}=1\) is equal to \(7\) and the minimum value is equal to \(2\). These are respectively the largest and the smallest eigenvalue of the matrix \(D=\text{diag}(7,4,2)\) of the quadratic form \(Q\). This holds in general:

Theorem: If \(A\) is a symmetric matrix and \(M=\max\{\mathbf{x}^TA\mathbf{x}\,:\,||\mathbf{x}||=1\}\) and \(m=\min\{\mathbf{x}^TA\mathbf{x}\,:\,||\mathbf{x}||=1\}\), then we have: \(M\) is equal to the largest eigenvalue of \(A\) and \(m\) is equal to the smalles eigenvalues of \(A\). Further we have: \(\mathbf{x}^TA\mathbf{x}=M\) if \(\mathbf{x}\) is an eigenvector (with \(||\mathbf{x}||=1\) of \(A\) corresponding to the eigenvalue \(M\) and \(\mathbf{x}^TA\mathbf{x}=m\) if \(\mathbf{x}\) is an eigenvector (with \(||\mathbf{x}||=1\) of \(A\) corresponding to the eigenvalue \(m\).

Proof: The matrix \(A\) is symmetric and therefore orthogonally diagonizable. Hence we have: \(A=PDP^T\) for ceratin orthogonal matrix \(P\) and diagonal matrix \(D\). Suppose that \(\mathbf{x}=P\mathbf{y}\), then we have: \(\mathbf{x}^TA\mathbf{x}=\mathbf{y}^TD\mathbf{y}\). Further we have: \(||\mathbf{x}||=||P\mathbf{y}||=||\mathbf{y}||\). Hence: \(||\mathbf{x}||=1\;\Longleftrightarrow\;||\mathbf{y}||=1\).

Suppose that \(P=\Bigg(\mathbf{u}_1\;\ldots\;\mathbf{u}_n\Bigg)\) and \(D=\text{diag}(\lambda_1,\ldots,\lambda_n)\) with \(\lambda_1\geq\ldots\geq\lambda_n\). Then we have \(\mathbf{x}^TA\mathbf{x}=\mathbf{y}^TD\mathbf{y}=\lambda_1y_1^2+\cdots+\lambda_ny_n^2\) and therefore:

\[M=\max\{\mathbf{x}^TA\mathbf{x}\,:\,||\mathbf{x}||=1\}=\max\{\mathbf{y}^TD\mathbf{y}\,:\,||\mathbf{y}||=1\}=\lambda_1\]

and

\[m=\min\{\mathbf{x}^TA\mathbf{x}\,:\,||\mathbf{x}||=1\}=\min\{\mathbf{y}^TD\mathbf{y}\,:\,||\mathbf{y}||=1\}=\lambda_n.\]

Further we have: \(M=\mathbf{x}^TA\mathbf{x}=\mathbf{y}^TD\mathbf{y}\) if \(\mathbf{y}=\begin{pmatrix}1\\0\\\vdots\\0\end{pmatrix}\) and therefore if \(\mathbf{x}=P\mathbf{y}=\mathbf{u}_1\) and \(m=\mathbf{x}^TA\mathbf{x}=\mathbf{y}^TD\mathbf{y}\) if \(\mathbf{y}=\begin{pmatrix}0\\\vdots\\0\\1\end{pmatrix}\) and therefore if \(\mathbf{x}=P\mathbf{y}=\mathbf{u}_n\).

Example: Find the maximum \(M\) and the minimum \(m\) of the quadratc form \(Q(\mathbf{x})=x_1^2+5x_2^2+5x_3^2-8x_1x_2+8x_1x_3\) subject to the constraint \(\mathbf{x}^T\mathbf{x}=1\) and find a unit vector \(\mathbf{x}\) such that \(Q(\mathbf{x})=M\) and a unit vector \(\mathbf{x}\) such that \(Q(\mathbf{x})=m\).

Note that \(Q(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\) with \(A=\begin{pmatrix}1&-4&4\\-4&5&0\\4&0&5\end{pmatrix}\). Then we have:

\begin{align*} |A-\lambda I|&=\begin{vmatrix}1-\lambda&-4&4\\-4&5-\lambda&0\\4&0&5-\lambda\end{vmatrix}=\begin{vmatrix}1-\lambda&-4&4\\ 0&5-\lambda&5-\lambda\\4&0&5-\lambda\end{vmatrix}=\begin{vmatrix}1-\lambda&-4&8\\0&5-\lambda&0\\4&0&5-\lambda\end{vmatrix}\\[2.5mm] &=(5-\lambda)\begin{vmatrix}1-\lambda&8\\4&5-\lambda\end{vmatrix}=(5-\lambda)(\lambda^2-6\lambda-27)=(5-\lambda)(\lambda-9)(\lambda+3). \end{align*}

This implies that \(M=9\) and \(m=-3\). Further we have:

\[M=9:\quad\begin{pmatrix}-8&-4&4\\-4&-4&0\\4&0&-4\end{pmatrix}\sim\begin{pmatrix}1&0&-1\\0&1&1\\0&0&0\end{pmatrix} \quad\Longrightarrow\quad\mathbf{x}=\pm\frac{1}{\sqrt{3}}\begin{pmatrix}1\\-1\\1\end{pmatrix}\]

and

\[m=-3:\quad\begin{pmatrix}4&-4&4\\-4&8&0\\4&0&8\end{pmatrix}\sim\begin{pmatrix}1&0&2\\0&1&1\\0&0&0\end{pmatrix} \quad\Longrightarrow\quad\mathbf{x}=\pm\frac{1}{\sqrt{6}}\begin{pmatrix}2\\1\\-1\end{pmatrix}.\]

We can also add some extra constraints:

Theorem: If \(A\) is a symmetric matrix with \(A=PDP^T\), where \(P=\Bigg(\mathbf{u}_1\;\ldots\;\mathbf{u}_n\Bigg)\) and \(D=\text{diag}(\lambda_1,\ldots,\lambda_n\) with \(\lambda_1\geq\cdots\geq\lambda_n\), then we have for each \(k\in\{1,2,\ldots,n-1\}\): the maximum of the quadratic form \(\mathbf{x}^TA\mathbf{x}\) subject to the constraints

\[\mathbf{x}^T\mathbf{x}=1,\quad\mathbf{x}^T\mathbf{u}_1=0,\;\ldots,\quad\mathbf{x}^T\mathbf{u}_k=0\]

is equal to the eigenvalue \(\lambda_{k+1}\) and \(\mathbf{x}^TA\mathbf{x}=\lambda_{k+1}\) if \(\mathbf{x}=\mathbf{u}_{k+1}\).

Example: Find the maximum of the quadratic form \(Q(\mathbf{x})=x_1^2+5x_2^2+5x_3^2-8x_1x_2+8x_1x_3\) subject to the constraints \(\mathbf{x}^T\mathbf{x}=1\) and \(\mathbf{x}^T\mathbf{u}_1=0\) with \(\mathbf{u}_1=\dfrac{1}{\sqrt{3}}\begin{pmatrix}1\\-1\\1\end{pmatrix}\) and find a unit vector \(\mathbf{x}\) for which this maximum is attained.

We have seen that \(Q(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\) with \(A=\begin{pmatrix}1&-4&4\\-4&5&0\\4&0&5\end{pmatrix}\) and that the eigenvalues are: \(\lambda_1=9\), \(\lambda_2=5\) and \(\lambda_3=-3\). The maximum subject to the constraints is equal to \(5\). Further we have:

\[\lambda_2=5:\quad\begin{pmatrix}-4&-4&4\\-4&0&0\\4&0&0\end{pmatrix}\sim\begin{pmatrix}1&0&0\\0&1&-1\\0&0&0\end{pmatrix} \quad\Longrightarrow\quad\mathbf{x}=\pm\frac{1}{\sqrt{2}}\begin{pmatrix}0\\1\\1\end{pmatrix}.\]

---

Last modified on May 2, 2021