# Leading eigenvector value problem as an optimisation problem for asymmetric matrices

As noted in 1806.05647, given a symmetric matrix $$A$$, the leading eigenvector value problem (LEVP)

$$Av = \lambda v,$$

where $$A = A^T \in \mathbb{R}^{n \times n}$$, $$\lambda$$ is the largest eigenvalue of $$A$$ and $$v$$ is the corresponding eigenvector, can be written as an unconstrained optimisation problem

$$\min_{x \in \mathbb{R}^n} f(x) \equiv \min_{x \in \mathbb{R}^n} \| A - xx^T\|^2_F,$$

where $$\| \cdot \|_F$$ denotes the Frobenius norm.

When the matrix $$A$$ is symmetric, the gradient of the function $$f(x)$$ is

$$\nabla f(x) = -4Ax + 4(x^Tx)x$$

and the optimal solution to the aforementioned optimisation problem can be shown to be $$\pm \sqrt{\lambda}v$$. All the coordinate-wise descent algorithms represented in the paper for computing the leading eigenvector depend on this result and the matrix $$A$$ being symmetric.

Is it possible to generalise this to the case when the matrix $$A$$ is not symmetric? In that case, the gradient is: $$\nabla f(x) = -2Ax -2A^Tx + 4(x^Tx)x$$

and the solution that was optimal for the symmetric matrix $$A$$ ( $$\pm \sqrt{\lambda}v$$) now is the optimal solution for $$\frac{1}{2}(A^T + A)$$ rather than $$A$$.

I believe so. Here is one way to show the claim. The function being minimized can be written in terms of the standard (Euclidean) norm on $$\mathbb{R}^n$$ as $$$$f(x) = || A - xx^T||_F^2 = tr\left[(A^T-xx^T)(A-xx^T)\right] = tr(A^TA)+ x^2\left[x^2-2 R(M,x)\right] = tr(A^TA)+ [x^2-R(M,x)]^2 - R(M,x)^2,$$$$ where $$x^2=x^Tx$$, $$M=\frac{A^T+A}{2}$$ and $$R(M,x)=\frac{x^TMx}{x^2}$$ is the Rayleigh quotient of $$M$$. To minimize $$f(x)$$, we thus need to make the second term vanish and find the largest value for the square of the Rayleigh quotient.
Since $$M$$ is real-symmetric, it can be diagonalized with real eigen-values $$\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n \in \mathbb{R}$$ (spectral theorem). Furthermore, the min-max theorem says that $$\lambda_1 \leq R(M,x) \leq \lambda_n$$, $$\forall x\in \mathbb{R}^n\setminus \{0\}$$ and so $$R(M,x)^2 \leq max(\lambda_1^2,\lambda_n^2)$$.
The Rayleigh quotient evaluated at the eigen-vector $$v_k$$ exactly returns the eigen-value $$\lambda_k$$, i.e. $$R(M,v_k)=\lambda_k$$. So $$x =\pm \sqrt{\lambda_k} v_k$$ (with care if $$\lambda_k<0$$) will make the second term of $$f(x)$$ vanish (and will in fact be a critical point). Therefore, the optimal solution is either $$\pm\sqrt{\lambda_1}v_1$$ or $$\pm\sqrt{\lambda_n}v_n$$ (depending on which of $$\lambda_1^2$$ or $$\lambda_n^2$$ is greater).
If $$M=(A^T+A)/2$$ symmetric positive-definite, then $$0<\lambda_1\leq \ldots\leq \lambda_n$$ and $$\pm\sqrt{\lambda_n}v_n$$ is optimal.