# Overdetermined homogeneous linear equation system - $A$ vs $A^TA$

Actually I am working with a overdetermined homogeneous system of linear equations $$Ax=0$$. In literature I found, that a least square result can be found with helpf of SVD. The solution is the eigenvector corresponding to the smallest eigenvalue of $$A^TA$$.

So far so good. But in some literature I could read, that one should look for the eigenvalue/eigenvector of $$A$$. Unfortunately I cannot find the literature, which says $$A$$ instead of $$A^TA$$.

Does the method change, if the system is not overdetermined?

• The least-squares solution to $Ax = 0$ is always $x=0$. I guess you mean $Ax = b$. Then, and if $A$ has full rank, the least squares solution is that of $A^TAx = A^Tb$, i.e., $x = (A^TA)^{-1}A^Tb$. Commented Aug 1, 2021 at 0:33
• I had in mind the non trivial solution for $Ax=0$. The solutions form a hyperspace, so another constraint is needed. In Literatur $||x||=1$ is mentioned, which I had in mind. I forgot to mention this. Commented Aug 1, 2021 at 14:59
• Then your system is not overdetermined, but underdetermined. The matrix $A$ is wide and fat and not slim and tall. Commented Aug 1, 2021 at 15:04
• “I had in mind 'the' nontrivial solution for $Ax=0$.” If there is a nontrivial solution to $Ax =0$, then there are infinitely many nontrivial solutions. In that case, you can find a nontrivial solution whose norm is as small as you like. Commented Jul 24, 2022 at 6:07

With the answer and the comments I finally could answer the question by myself and solve my confusion. Thanks again for putting me on the right track. Both leads to a valid solution.

Edit: And as user amsmath commented, it always holds that $$min_{||x||=1}||Ax|| = min_{||x||=1}\sqrt{\langle A^TAx, x \rangle}$$ which is always (!) the square root of the smallest eigenvalue of $$A^TA$$ (and at the same time the smallest singular value of $$A$$)

An overdetermined homogeneous linear equation system can be represented as $$Ax=0$$, where $$A\in R^{m\times n}$$ with $$m>n$$ subject to $$||x||=1$$. Desired is a non trivial solution ($$x\neq 0$$), which minimizes $$||Ax||$$. Solutions form a hyperspace. If $$x_0$$ is a solution, then $$\kappa x_0$$ for $$\kappa \in R$$ is also a solution.

### Case 1 - Solution is the right-singular vector corresponding to the smallest singular value of $$A$$

Edit: I was mixing up eigenvalues and singular value. Beeing precise helps to improve understanding. In that post the difference of eigenvalues and singular values is discussed.

We are looking for an $$x$$ that minimizes $$||Ax||$$ subject to $$||x||$$. The SVD decomposition of $$A$$ leads to $$A = UDV^T,$$ where $$U\in R^{m\times m}$$, $$D\in R^{m\times n}$$, and $$V \in R^{n\times n}$$.

Since $$U$$ is an orthogonal matrix $$||Ax||=||UDV^Tx||$$ leads to $$||Ax||=||DV^Tx||.$$

$$V$$ is also an orthogonal matrix. So if $$||x||=1$$ holds, then $$||V^Tx||=1$$ holds, too. We substitute $$V^Tx$$ with $$y$$ and minimizing $$||Dy||c$$ subject to $$||y||=1$$. The matrix $$D$$ is a diagonal matrix $$D=\begin{pmatrix} d_1 & 0 & \dots & 0\\ 0 & d_2 & \dots & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \dots & d_n\\ 0 & 0 & \dots & 0\\ \vdots & \vdots & & \vdots\\ 0 & 0 & \dots & 0\\ \end{pmatrix}\in R^{m\times n},$$ with $$d_1 > d_2 > \dots > d_n$$ we can minimize $$||Dx||$$ by chosing $$y = \begin{pmatrix}0\\0\\ \vdots \\ 1\end{pmatrix} \in R^{n\times 1},$$ which satisfy $$||y||=1$$. The substitution of $$V^T$$ with $$y$$ leads to $$x=Vy=\begin{pmatrix}V_{1n}\\V_{2n}\\\vdots\\V_{nn}\end{pmatrix}$$ $$\square$$

### Case 2 - Solution is the eigenvector corresponding to the smallest eigenvalue of $$A^TA$$.

Applying Lagrange function \begin{align}L(x,\lambda) & := ||Ax|| + \lambda (1-||x||) \\& = x^TA^TAx + \lambda (1-x^Tx) \end{align} Critical points of the Lagrange function are found by equaling derivatives to zeros \begin{align} \frac{\partial L(x,\lambda)}{\partial x} & = 2A^TAx - 2\lambda x = 0\\ \frac{\partial L(x,\lambda)}{\partial \lambda} & = 1- x^Tx = 0 \end{align} First partial derivative can be rewritten as the characteristic polynom $$(A^TA - \lambda I)x = 0$$ of $$A^TA$$. So every eigenvector $$x$$ with corresponding eigenvalue $$\lambda$$ is a critical point and hence a solution for the equation above. We choose the smallest eigenvalue to minimize $$||Ax||$$. Combining equations lead to \begin{align}||Ax|| &= x^TA^TAx \\ &= x^T\lambda x\\ &= \lambda x^Tx\\ &=\lambda||x||\\& = \lambda \end{align} Therefore the solution is the eigenvector of $$A^TA$$ with the smallest corresponding eigenvalue. $$\square$$

• "Solution is the eigenvector corresponding to the smallest eigenvalue of $A$" Well, if $A$ is not square, it does not have eigenvalues. The concept of eigenvalues is only defined for square matrices. Commented Aug 1, 2021 at 22:28
• $\min_{\|x\|=1}\|Ax\| = \min_{\|x\|=1}\sqrt{\langle A^TAx,x\rangle}$, which is always (!) the square root of the smallest eigenvalue of $A^TA$ (and at the same time the smallest singular value of $A$). Commented Aug 1, 2021 at 22:33
• Your are right. I was not precise in the text and revised it. Furthermore the relation you mentioned in second comment was not clear to me. I also added it into the text. Commented Aug 1, 2021 at 23:19

If the system is not over-determined then there should be a solution, so you should try to solve the original problem,

$$A x = 0.$$

More generally, it sounds like you want to do something like minimizing the norm of the vector, $$A x$$. But of course you'd just choose $$x=0$$. So do you want to instead minimize the norm of $$A x$$ for a fixed magnitude of $$x$$?. If so, the way I'd do it is to minimize $$(A x)^2 = x^T A^T A x$$ subject to the condition $$x^T x = 1$$. I'd do that by adding the Lagrange multiplier term and enforcing the first-order conditions on:

$$x^T A^T A x + \lambda (x^T x - 1).$$

That is, I'd differentiate it with respect to the vector $$x$$ and set it equal to zero, yielding:

$$A^T A x + \lambda x = 0.$$

Consequently, indeed, if this is what you want then your answer should be an eigenvector of $$A^T A$$, specifically any one with the lowest eigenvalue. I think similar analysis applies to the complex case where the transpose is replaced with the conjugate transpose.

• Thanks for your quick reply. In deed I forgot to mention some details in my question. And with your answer I was able to understand more details. I am looking for a non trivial solution of $Ax=0$. In Literatur the condition $||x||=1$ is used. So the task is then to minimize $||Ax||$ with subject $||x||=1$. One best solution fitting the constraint is the eigenvector of $A$ corresponding to the smallest eigenvalue. Next question, which comes up to me: If I want to minimize $(Ax)^2$ with subject $||x||=1$, do I then have to look for the eigenvector of $A^TA$ corresp. to smallest eigenvalue? Commented Aug 1, 2021 at 15:12
• Thanks @Blueshark glad it was helpful. Per my answer, yes, you want to find the eigenvector corresponding to the lowest eigenvalue of $A^T A$. Commented Aug 2, 2021 at 2:35

Both the SVD method and the Lagrange method for the non-trivial ‘solution’ of overdetermined homogeneous simultaneous linear equations are described by Patterson (2012). I put the word ‘solution’ in single quote marks as these are almost always not exact solutions, rather a least squares fit. Also note, Patterson (2012) is an application to an ecological network problem, and may fall short of a more complete mathematicial treatment of the topic … that said, I can’t find a a treatment of these 2 solution methods in the more mathematical journals/literature and I would be grateful if anyone could provide me with a reference to any such publication. Reference: Patterson,M.G. 2012. Are all processes equally efficient from an emergy perspective? Analysis of ecological and economic networks using matrix algebra methods. Ecological Modelling Volume 226 pp. 77-91

• Welcome to Math Stack. It seems you are posing new questions here. Do you feel you are also providing an answer to the original question? Commented Jul 24, 2022 at 5:19
• Blueshark (above) provided an excellent answer to the original question by outlining 2 solutions to the problem: Case 1 (SVD) and Case 2 (Lagrange method). I was simply asking where such an answer might appear in the journal or academic literature. (I cite one very applied journal article where I used both of these methods. But I am hoping that there may be a more mathematical treatment that someone may be able to identify). So I feel I am not “posing a new question”, rather seeking extra information about Blueshark’s answer to the original question. Commented Jul 25, 2022 at 0:46