Eigenvectors of a covariance matrix with only positive elements - Cross Validated most recent 30 from stats.stackexchange.com 2019-07-17T17:29:27Z https://stats.stackexchange.com/feeds/question/38571 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://stats.stackexchange.com/q/38571 5 Eigenvectors of a covariance matrix with only positive elements Grapy https://stats.stackexchange.com/users/14607 2012-10-03T14:09:33Z 2014-10-02T23:14:22Z <p>If all the elements of a positive-definite covariance matrix are positive, how can I prove that the coefficients [elements] of the first principal component [first eigenvector] are all of the same sign, and the coefficients [elements] of all other principal components [eigenvectors] cannot all be of the same sign?</p> <p>This is Problem 11.11 from "Multivariate Statistical Analysis" by Anderson, 3rd ed. I have tried to prove it for several days...</p> https://stats.stackexchange.com/questions/38571/-/38574#38574 4 Answer by Peter Flom for Eigenvectors of a covariance matrix with only positive elements Peter Flom https://stats.stackexchange.com/users/686 2012-10-03T14:21:14Z 2012-10-03T14:21:14Z <p>If the signs of the coefficients are all of the same sign it indicates that they are all measuring the first component in the same direction. If you reverse one of the variables (e.g. by multiplying it by -1) you ought get something different. The signs of the first component do not all need to be positive; indeed, when I run this example from <code>R prcomp</code></p> <pre><code>prcomp(USArrests, scale = TRUE) </code></pre> <p>all the signs are negative (but that could be different when you run it)</p> <p>If I then run </p> <pre><code>prcomp(~ Murder + Assault + Rape, data = USArrests, scale = TRUE) </code></pre> <p>all the signs are again negative on PC1 but if I modify it:</p> <pre><code>attach(USArrests) rapeinv &lt;- Rape*-1 prcomp(~ Murder + Assault + rapeinv, scale = TRUE) </code></pre> <p>then two signs are negative but the one for rapeinv is positive.</p> <p>Often, in practice (as here) the first component is capturing something general about the data (here, crime rate) so it is frequently the case that the first PC will have all its signs the same, but it is not necessarily the case.</p> https://stats.stackexchange.com/questions/38571/-/38704#38704 4 Answer by kjetil b halvorsen for Eigenvectors of a covariance matrix with only positive elements kjetil b halvorsen https://stats.stackexchange.com/users/11887 2012-10-05T01:45:55Z 2014-10-02T09:52:27Z <p>With your new information, that <strong>all the components of the positive-definite matrix are positive</strong>, it becomes easy. While it follows directly from the <a href="http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem" rel="nofollow">Perron-Frobenius theorem</a> (which is valid for square matrices with non-negative elements, symmetric or not), in the symmetric case it is much easier.</p> <p>Let the positive-definite matrix be $S$. The eigenvector corresponding to the largest eigenvector is the vector $x$ obtaining the maximum in the following problem: $$\lambda_{\mathrm{max}} = \mathrm{max}_{\{x \colon \| x\|=1\}} x^T S x$$(that is, the "argmax") where $\lambda_{\text{max}}$ is the largest eigenvalue.</p> <p>Suppose to get a contradiction that $x_1$ is negative, while the other components of $x$ are non-negative. We can write $$x^T S x = x_1 S_{11} x_1+2x_1 \sum_{j=2}^m s_{1j} x_j + \sum_{i=2}^m \sum_{j=2}^m x_i s_{ij} x_j$$ Note that the first and third terms are positive while the second term is negative, and we can get a strictly larger value by switching the sign of $x_1$, which respects the restriction on norm. That gives the contradiction you need. A similar argument can be written for any other pattern of negative/positive sign.</p> https://stats.stackexchange.com/questions/38571/-/117688#117688 4 Answer by whuber for Eigenvectors of a covariance matrix with only positive elements whuber https://stats.stackexchange.com/users/919 2014-10-02T22:25:57Z 2014-10-02T22:25:57Z <p>The solutions to the two questions follow in a straightforward manner from the definitions, but some care is needed in the analysis. I offer this post to fill in some gaps in the previous ones, to make the solution self-contained (without relying on any advanced or specialized theorems), and to provide a solution to the second question, which so far has not been offered.</p> <hr> <p>Let $\mathbb A$ be the covariance matrix, of dimensions $n$ by $n$. It is symmetric and positive-definite by assumption. Therefore (these are standard results in the study of such matrices) there exists a basis of $n$ <em>nonzero</em> eigenvectors $E=(e_1, e_2, \ldots, e_n)$ for which</p> <ol> <li><p>The $e_i$ all have real (not merely complex) coefficients;</p></li> <li><p>$\mathbb A e_i = \lambda_i$ for non-negative real (not merely complex) numbers $\lambda_i$, the <em>eigenvalues</em>;</p></li> <li><p>We may therefore order the eigenvectors so that $\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n \gt 0$; </p></li> <li><p>The eigenvectors are mutually orthogonal: $e_i^\prime e_j = 0$ whenever $i\ne j$; and </p></li> <li><p>We may normalize the eigenvectors (by dividing each one by $\sqrt{e_i^\prime e_i}$ if necessary) to make them all of unit length.</p></li> </ol> <p>These are the basic facts worth remembering, because they (greatly) simplify our understanding and analysis of such matrices, which are ubiquitous in statistical theory and practice. The remainder of this post exploits these properties to address the two questions.</p> <p>Because $E$ is a basis, any <em>arbitrary</em> vector $x$ has a unique expansion as a linear combination of eigenvectors,</p> <p>$$x = x_1 e_1 + x_2 e_2 + \cdots x_n e_n$$</p> <p>for real numbers $x_1, x_2, \ldots, x_n$ determined by $x$. Facts (4) and (5) let us calculate that</p> <p>$$|x|^2 = x_1^2 + x_2^2 + \cdots + x_n^2$$</p> <p>and property (2) implies</p> <p>$$|\mathbb A x|^2 = \lambda_1^2 x_1^2 + \lambda_2^2 x_2^2 + \cdots + \lambda_n^2 x_n^2.$$</p> <p>It is clear--and is an easily proven elementary inequality--that when $|x|^2=1$, the latter is maximized when $x_j=0$ for all $j$ where $\lambda_j \lt \lambda_1$. (Provided $\lambda_1$ is unique-- that is, $\lambda_i \lt \lambda_1$ for $i=2, 3, \ldots, n$--there are exactly two solutions: $x_1=\pm 1$ (and $x_i=0$ for $i=2, 3, \ldots, n$), whence $x = \pm e_1$.)</p> <p><strong>The first question</strong> concerns the original coordinates in which the matrix and the eigenvectors were originally written. Writing $e_1 = (e_{11}, e_{12}, \ldots, e_{1n})$ in those coordinates, suppose there exist indexes $j$ for which $e_{1j}\lt 0$. Let $f$ be the vector obtained by negating all such $e_{1j}$. Because $e_{1j}^2 = (-e_{1j})^2$, this does not change the norm, whence $|f|=1$ (by fact (5)). However, this process increases $|\mathbb A e|$ because--by assumption--multiplication by $\mathbb A$ consists of taking linear combinations with <em>positive</em> coefficients and the change from $e_1$ to $f$ has actually turned what were subtractions of positive values into additions of positive values. Since $|\mathbb A e|$ was maximal, we conclude that $|\mathbb A f|$ is maximal and $f$ is an eigenvector with eigenvalue $\lambda_1$. We may therefore take $e_1$ to be $\pm f$, but either way all its components will have the same sign.</p> <p>As an (important) aside, note that <strong>all the components of $e_1$ must be positive:</strong> none can be zero. This is because (a) $e_1$ is nonzero, whence it has at least one nonzero component and (b) in computing the product $\mathbb A e_1 = \lambda_1 e_1$ (fact (2)) all the products being added up are sums of nonnegative numbers and at least one (obtained from a nonzero component of $e_1$) is nonzero. That shows all the components of $\lambda_1 e_1$ are nonzero, but since $\lambda_1 \gt 0$ (fact (3)), all components of $e_1$ must be nonzero, too.</p> <p><strong>The second question</strong> asserts that the remaining eigenvectors, $e_2, e_3, \ldots, e_n$, must have some negative components when written in the original basis. Consider one of them, say $e_j$ and write it as $e_j = (e_{j1}, e_{j2}, \ldots, e_{jn})$ in the original basis. Then from fact (4) $e_j$ is orthogonal to $e_1$:</p> <p>$$0 = e_1^\prime e_j = e_{11}e_{j1} + e_{12}e_{j2} + \cdots + e_{1n}e_{jn}.$$</p> <p>Since--as we showed in the aside--all the $e_{1i} \gt 0$, the only way this linear combination can equal zero is for at least one $e_{ji} \lt 0$.</p> <hr> <p>A more delicate version of these results can be obtained when the components of $\mathbb A$ are merely assumed to be nonnegative. What changes is that the first principal component may have zeros (as originally expressed) and some of the other principal components may also have entirely nonnegative entries, too. As an example, take $\mathbb A$ to be the $2\times 2$ identity matrix and let the first two principal components (which are not unique!) be $e_1=(1,0)$ and $e_2=(0,1)$.</p>