# Maximum and minimum ratio of matrix calculation

Suppose you have a matrix :

$$A = \begin{pmatrix} 13 & -4 & 2 \\ -4 & 13 & -2 \\ 2 & -2 & 10 \end{pmatrix}.$$

I want to find the maximum and minimum values of the ratio $$\frac{x'Ax}{x'x}$$ where $x =(x_1,x_2,x_3)$ is nonzero. Is there a way you can figure this out manually?

-
Do I have to write a program to calculate this? – lord12 Sep 9 '12 at 23:10

Since it's a symmetric matrix whose entries are real, it can be diagonalized by an orthogonal matrix $G$. That is the spectral theorem. And remember: an orthogonal matrix is a square matrix $G$ with real entries whose inverse is its transpose, so you have $G'G = I$. So you get $$A= G'\begin{bmatrix} \lambda_1 & 0 & 0 \\ 0 & \lambda_2 & 0 \\ 0 & 0 & \lambda_3 \end{bmatrix}G = G'\Lambda G.$$ By permuting rows of $G$, you can do this in such a way that $\lambda_1>\lambda_2>\lambda_3$.

Consequently $$\frac{x'Ax}{x'x} = \frac{x'(G'\Lambda Gx}{x'(G'G)x} = \frac{(x'G')\Lambda(Gx)}{(x'G')(Gx)} = \frac{(Gx)'\Lambda (Gx)}{(Gx)'(Gx)} = \frac{y'\Lambda y}{y'y} =\frac{\lambda_1 y_1^2 + \lambda_2 y_2^2 + \lambda_3 y_3^2}{y_1^2+y_2^2+y_3^2}.$$ If $(y_1,y_2,y_3)=(c,0,0)\ne(0,0,0)$, then the value of the fraction is $\lambda_1$, and similar comments apply to the other two $\lambda$s. What remains is to show that if more than two coordinates of $(y_1,y_2,y_3)$ are nonzero, then the value of the fraction is a weighted average of the $\lambda$s, so the value is somewhere between what it would be in the opposite extreme cases.

The values of $\lambda_i$, $i=1,2,3$ are eigenvalues, and are therefore the zeros of the characteristic polynomial.

-
Just to add, even if $A$ was not symmetric one could simply re-write $x'Ax=\frac{1}{2}x'(A'+A)x$ and using the eigenvalues/eigenvectors of $A'+A$ repeat the above. – jkn Sep 9 '12 at 23:32

I think you may have difficulty calculating the eigenvalues manually. They happen to be $18$ and $9$ (the latter with multiplicity $2$), so the minimum and maximum values of the ratio are $9$ and $18$.

EDIT: However, you may notice (well, I didn't until I found the eigenvalues by computer) that there is some symmetry involving the first two coordinates, and this might lead you to find one eigenvector: $$A \pmatrix{1\cr 1\cr 0\cr} = 9 \pmatrix{1 \cr 1\cr 0\cr}$$ Thus one eigenvalue is $9$. By looking at $A$ on the orthogonal complement of this eigenvector, we get a $2 \times 2$ matrix whose eigenvalues are easy to find by hand.

-
I was just wondering if you use a program like R or MATLAB to determine those eigenvalues or a standard method? – lord12 Sep 9 '12 at 23:56
I used Maple 16. – Robert Israel Sep 9 '12 at 23:58
Since the eignevalues are rational, it shouldn't be hard to find them manually. They're roots of a third-degree polynomial with integer coefficients. – Michael Hardy Sep 10 '12 at 17:22
The characteristic polynomial is $t^3-36t^2+405t-1458$. Computing this by hand is moderately tedious, and then since $1458 = 2 \times 3^6$ you might try various factors of that before getting one that is a root. Not something I'd like to do by hand, but to each his own. – Robert Israel Sep 10 '12 at 18:18