Use Lagrange's method to find the maximum value

Use Lagrange's method to find the maximum value of $\langle A\mathbf{x},\mathbf{x}\rangle$ subject to condition $\langle \mathbf{x},\mathbf{x}\rangle=1$ and $\langle \mathbf{u}_1,\mathbf{x}\rangle =0$ where $\mathbf{u}_1$ is a non zero vector in $N(s_1^2I_n-A^TA)$, $s_1$ is the largest singular value of A and $A=A^T \in \mathbb{R}^{n\times n}$.

Can anybody please explain me how to proceed with this question?

-
Maybe a stupid question, but what is $N(s_1^2I_n-A^TA)$ ? – k1next Jan 31 '13 at 13:31
Just a guess: the null space of the matrix $s_1^2 I_n - A^T A$? – Siminore Jan 31 '13 at 15:00
N represents the null space – aneps Jan 31 '13 at 18:50

This is connected to something proved in various places in MS (for instance Question related to Lagrange multipliers): the maximum of a quadratic form $Q$ on the unit sphere of a real euclidean space $E$ is the biggest eigenvalue of the matrix of $Q$ wrt any ortonormal basis of $E$. So we take $E\subset\mathbb R^n$ defined by $\langle \mathbf{u}_1,\mathbf{x}\rangle =0$ and $Q$ is the restriction to $E$ of $\langle A\mathbf{x},\mathbf{x}\rangle$. Thus one has to describe the eigenvalues of $Q$ looking carefully at $\mathbf{u}_1$. This can be done using the Spectral Theorem: there is always an orthonormal basis consisting of eigenvalues (an spectral basis). Many assertions that follows are more or less direct consequences of this fact.

First, as $s_1$ is an eigenvalue of $A$, $s_1^2$ is one of $A^TA=A^2$ ($A$ is symmetric). In fact, the eigenspace of $s_1^2$ is that $N$ containing $\mathbf u_1$, and there are two possibilities:

Case 1: $-s_1$ is not an eigenvalue of $A$. Then $N=N(s_1I-A)$ and $\mathbb R^n$ splits into an orthogonal sum $N\oplus F$, were $F$ is the sum of the other eigenspaces of $A$. This can be seen using an spectral basis for $A$. Now:

$\quad$ (i) If $\dim(N)=1$, that is, $s$ has multiplicity $1$, $E=F$ and the matrix of $Q$ wrt an orthonormal basis of $F$ consisting of eigenvectors of $A$ has the eigenvalues of $A$ except $s$. Thus the maximum we look for is the maximum eigenvalue of $A$ smaller than $s_1$.

$\quad$ (ii) If $\dim(N)>1$, we find ${\mathbf u}_2\in N$ with norm $1$ and orthogonal to $\mathbf u_1$, so that $Q(\mathbf u_2)=s_1$, being maximum on $\|\mathbb x\|=1$, is also the maximum we seek.

Case 2: $-s_1$ is also an eigenvalue of $A$. Then $N$ is the sum of the eigenspace of $s_1$ and that of $-s_1$, which can give any maximum $\le s_1$. For instance, for $n=2\$ let $A$ be the diagonal matrix $D(1,-1)$. Then $\mathbf u_1$ can be any vector in $\mathbb R^2$ so that the maximum of $Q$ we are interested in can be any number between $s_1=1$ and $-1$. Still, one can at least say as in (ii) above (by the same argument):

$\quad$ If $\dim(N)>1$, $s_1$ is the maximum we seek.

-