Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Do I have to write a program to calculate this? –  lord12 Sep 9 '12 at 23:10
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
1  
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.