Writing a real symmetric matrix $U^tAU$

Question

Writing a real symmetric matrix $M$, into the form $$ M = U^tAU $$ is possible, since a real symmetric matrix in an inner product space is self-adjoint. You can diagonalize it with an ONB (that is, $U^{-1} = U^t$).

What if I only require $A$ diagonal and $U$ invertible(not necessarily unitary)? What are all the possible solutions of $A$ and $U$, if such real symmetric $M$ is given?

---

Here is the original question I encountered.

Let $f(x,y) = x^2+4xy-10x+5y^2-24y+35$. Find the minimum of $f$.

There are clearly various other ways to solve this problem, but I wanted to do it in a linear algebraic way(a rather unnecessarily complex way). I observed that this looks like a quadratic form, and tried to solve it using the method of orthonormal diagonalization, i.e. writing $$ f(x,y) = \begin{pmatrix} x& y& 1\end{pmatrix} \begin{pmatrix} 1& 2& -5\\ 2& 5& -12\\ -5& -12& 35\\ \end{pmatrix} \begin{pmatrix} x\\ y\\ 1\end{pmatrix} $$ yet solving the characteristic polynomial is a rather big computation. Soon I saw other person's solution- writing the original function into $$(x+2y-5)^2+(y-2)^2+6$$ or in the language of linear algebra, writing it to the form $M = U^tAU$

$$ \begin{pmatrix} 1& 2& -5\\ 2& 5& -12\\ -5& -12& 35\\ \end{pmatrix} = \begin{pmatrix} 1& 0& 0\\ 2& 1& 0\\ -5& -2& 1\\ \end{pmatrix} \begin{pmatrix} 1& 0& 0\\ 0& 1& 0\\ 0& 0& 6\\ \end{pmatrix} \begin{pmatrix} 1& 2& -5\\ 0& 1& -2\\ 0& 0& 1\\ \end{pmatrix} $$ which is different from my attempt at writing $M = U^tAU$(in my case of diagonalization, neither 1 nor 6 is an eigenvector of the original matrix). So my question is, what is the general possible way to decompose $M$ into $U^tAU$?

---

(unrelated to the question, but) Now I noticed that I can ignore the x y, and constant terms and then do orthonormal diagonalization. After the diagonalization, I can express the rest $px+qy$ terms into the linear combination of the eigenvector, after which then I can use the method of completing the square.

Answer 1

The appropriate method is diagonalization by congruence. Given a symmetric matrix $A$ over any field of characteristic other than 2, we can always find a non-singular matrix $U$ such that $U^TAU$ is diagonal.The method is very easy and has nothing to do with eigenvalues. All you need to do is repeatedly make a linear change of variable to eliminate the off- diagonal terms or, in the exceptional case when all the remaining diagonal terms are 0, make a linear change of variables to force a non-zero diagonal term. In a problem like yours, start by just diagonalizing the quadratic part but keep track of what happens to the linear part. In your problem, all you need to do is let $u=x+2y,v=y$ and you have a quadratic expression with no $uv$ term.

Answer 2

Partial answer:

If I am not mistaken, \begin{align} &\begin{pmatrix} 1& 0& 0\\ 2& 1& 0\\ -5& -2& 1\\ \end{pmatrix} \begin{pmatrix} 1& 0& 0\\ 0& 1& 0\\ 0& 0& 6\\ \end{pmatrix} \begin{pmatrix} 1& 2& -5\\ 0& 1& -2\\ 0& 0& 1\\ \end{pmatrix}\\ &=\begin{pmatrix} 1& 0& 0\\ 2& 1& 0\\ -5& -2& \sqrt{6}\\ \end{pmatrix} \begin{pmatrix} 1& 2& -5\\ 0& 1& -2\\ 0& 0& \sqrt{6}\\ \end{pmatrix}\,. \end{align} More generally, if the $U$ is an upper triangular matrix and $D$ a diagonal matrix having nonnegative elements we can always bring $M=U^\top DU$ into the form $M=L^\top L$ where the rows of $L$ are those of $U$ multiplied with the square roots of $D$'s diagonal elements.

We know from the Cholesky decomposition that $M=L^\top L$ exists if and only if $M$ is symmetric and positive semidefinite.

Answer 3

This is also an interesting way to solve it please have a look,

Theorem

If $K$ is a symmetric positive definite matrix, then the quadratic form $P(X)=X^TKX-2X^Tf+c$ has a unique minimizer, which is the solution to the linear system $KX=f$ namely $X=K^{-1}f$ and the minimum value of $P(X^*)=P(K^{-1}f)=c-f^TK^{-1}f=c-f^TX^*=c-(X^*)^TKX^*$.

Let $f(x,y) = x^2+4xy-10x+5y^2-24y+35$.

$$ f(x,y) = \begin{pmatrix} x& y\end{pmatrix} \begin{pmatrix} 1& 2\\ 2& 5 \end{pmatrix} \begin{pmatrix} x\\ y\end{pmatrix} -2\begin{pmatrix} x& y\end{pmatrix}\begin{pmatrix} 5& 12\end{pmatrix}^T+35.$$

and for this quadratic form $f(x,y)$, minimum attain at $X^*=K^{-1}f$ where $K=\begin{pmatrix} 1& 2\\ 2& 5 \end{pmatrix}$ and $f=\begin{pmatrix} 5& 12\end{pmatrix}$

and hence $X^*=(1,2)$ implies $f(1,2)=6.$