3
$\begingroup$

Let $\mathrm A = \mathrm x \mathrm x^{T}$, where $\mathrm x \in \mathbb R^n$. As $\operatorname*{rank}{\mathrm A} = 1$, is there an efficient way to find the eigenvectors of $\mathrm A$?

$\endgroup$
  • $\begingroup$ If you use $x=(a,b)$ you see that the determinant is $=0$. Then you see that by construction all columns are linearly dependent, in the general case. $\endgroup$ – Rudi_Birnbaum Aug 20 '16 at 8:05
  • 1
    $\begingroup$ You can use Gram-Schmidt to find an orthonormal basis of the $(n-1)$-dimensional null space. $\endgroup$ – Rodrigo de Azevedo Aug 20 '16 at 8:22
7
$\begingroup$

First of all, $\|X\|^2$ is an eigenvalue of $(XX^T)$ associated with eigenvector $X$. The proof is as follows;

$$(XX^T)X=X(X^TX)=X\|X\|^2=\|X\|^2X=\lambda X.$$

What are the other eigenvectors and eigenvalues ?

Let $\{Y_1,\cdots Y_{n-1}\}$ be a basis of the ($(n-1)$-dimensional) orthogonal set $X^{\perp}$ of $X$.

$Y_k$ being, by definition, orthogonal to $X$, we have $X^TY_k=0$, then:

$$(XX^T)Y_k=X(X^TY_k)=X0=0=0Y_k$$

proving that any $Y_k$ is an eigenvector of $(XX^T)$ associated with eigenvalue $0$ (in other words $Y_k \in ker(XX^T)$).

Edit: Let us now address (shortly) the issue of finding efficiently a basis $\{Y_1,\cdots Y_{n-1}\}$ .

  • If it is a software concern, such a basis can be obtained in a snap with almost all scientific software, for example in Matlab with null(x*x').

  • on the more theoretical side, it has to be known that most calculations (like obtaining the null space as before) are done by using Singular Value Decomposition (SVD). This decomposition has become one of the most central tools of all Linear Algebra.

  • But SVD is not aimed at hand computation... If this is your concern, for very small values of $n$, I would say that it is rather easy with the little trick of obtaining a basis with an upper triangle of zeros (in order to be sure at once that all vectors $B_k$ are independant). This also what is called "echelon form". An example will make it clear:

$$\text{with} \ X=\begin{pmatrix}1\\2\\4\\1\end{pmatrix} \ \ \rightarrow \ \ B_1=\begin{pmatrix}2\\-1\\0\\0\end{pmatrix}, \ B_2=\begin{pmatrix}0\\-2\\1\\0\end{pmatrix}, \ B_3=\begin{pmatrix}0\\0\\-1\\4\end{pmatrix}$$

(the upper triangle of zeros appears when column vectors $B_1,B_2,B_3$ are gathered).

$\endgroup$
  • $\begingroup$ why not vote up my comment? $\endgroup$ – Rudi_Birnbaum Aug 20 '16 at 8:22
  • 7
    $\begingroup$ @R_Berger I am sorry but my answer is negative for 2 reasons, ethical and scientific 1) it is not a good practise to ask for upvoting 2) I do often upvote answers that bring something. But yours, I am sorry, is not coherent: why not consider the $n=2$ case but what do you do with your partial conclusion (i.e., det=0) because you don"t make, out of that, any conclusion. You jump to the general case and do not answer to the question of the OP: what are the eigenvectors ? $\endgroup$ – Jean Marie Aug 20 '16 at 8:44
  • $\begingroup$ Thank you all for the answers they helped me a lot :) $\endgroup$ – Reza_va Aug 20 '16 at 8:51
  • $\begingroup$ I have added an Edit to my answer. $\endgroup$ – Jean Marie Aug 20 '16 at 12:24
  • $\begingroup$ Well, I think it also clear to you, that there is a slight difference between asking for upvoting and asking for reasons of not upvoting. $\endgroup$ – Rudi_Birnbaum Aug 20 '16 at 12:52
1
$\begingroup$

One way to calculate eigenvectors of $xx^T$ is to perform the QR factorization of $x$ using Householder reflections. In this case eigenvectors can be given explicitly.

Let $e_1$ is the first column of the identity matrix and let $$P = I - \frac{2}{\|x-e_1\|^2_2}(x-e_1)(x-e_1)'$$ In can be easily verified directly that:

  1. $P$ is orthogonal matrix
  2. $Px = e_1$
  3. $Pe_1 = x$

Therefore columns of $P$ gives required eigenvectors of $xx^T$ and the first column of $P$ is equal to $x$. The Schur factorization of $xx'$ is given by $$xx' = P (e_1e_1^T) P'$$ From this we see, that $xx'$ has one eigenvalue equal to $1$ and $n-1$ eigenvalues equal to $0$.

$\endgroup$
  • $\begingroup$ In what sense do you think it is "the simplest way" ? $\endgroup$ – Jean Marie Aug 20 '16 at 10:34
  • $\begingroup$ Well, this can not be proven. I have edited this answer $\endgroup$ – Pawel Kowal Aug 20 '16 at 10:57
  • $\begingroup$ the nonzero eigenvalue need not be 1, unless $x$ is normalized $\endgroup$ – davyjones Aug 22 '16 at 1:53
1
$\begingroup$

It’s fairly easy to show, as JeanMarie does in his answer, that the eigenvalues of $A$ are $1$ and $0$, with eigenspaces the span of $x$ and its orthogonal complement $x^\perp$, respectively.

If you already have $x$, generating a basis for its orthogonal complement is trivial. Let $x=(x_1,...x_n)^T$ and assume for the moment that $x_1\ne0$. Then a basis for $x^\perp$ is given by the vectors $b_k=(x_k,0,\dots,-x_1,\dots,0)^T$ for $k=2$ to $n$, where the $-x_1$ is the $k$th component of the vector. That is, for the vector $b_k$, put $-x_1$ in the $k$th slot (replacing the $x_k$ of the vector $x$), make the first component $x_k$, and fill the rest of the vector with zeroes. It should be obvious from inspection that these vectors are linearly independent and that $x\cdot b_k=0$. If $x_1=0$, use the first non-zero component instead and fill in the corresponding slot in the basis vector instead of using the first slot. For example, with $x=(4,-3,2,1)^T$ we have $b_2=(-3,-4,0,0)^T$, $b_3=(2,0,-2,0)^T$ and $b_3=(1,0,0,-4)^T$, while with $x=(0,1,2,3)^T$, we’d have $b_2=(-3,0,0,0)^T$, $b_3=(0,2,-3,0)^T$ and $b_4=(0,1,0,-3)^T$.

If you don’t know $x$, it’s fairly simple to extract it from $A$. One way is to row-reduce $A$. The first row of the reduced matrix will be a scalar multiple of $x$, which is just as good as having $x$ itself for this purpose. However, it might be more efficient to take advantage of $A$’s structure. The elements along the main diagonal are $a_{ii}=x_i^2$, so the absolute values of the $x_i$ can be recovered by taking square roots along the diagonal. You can then examine the signs of the off-diagonal elements, which are of the form $a_{ij}=x_ix_j$, to determine the signs of the $x_k$ (up to an overall scalar multiplier of $\pm 1$, that is).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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