Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In an $n\times n$ non negative row stochastic matrix (rows sum up to 1).
The entries of the stochastic matrix I have represent directed links between countries.

  1. Why is the first right eigenvector a vector of ones and what does that imply in that case?
  2. Why do we want to calculate the second right eigenvector in that case?
share|improve this question
    
Please check that I haven't changed your intended meaning unintentionally. –  Gigili Mar 11 '13 at 14:44
    
It's easy to check a vector of ones is the right eigenvector of a stochastic matrix. It implies rows summing to 1. –  chaohuang Mar 11 '13 at 17:05
    
The entries of the stochastic matrix I have represent directed links between countries. What would an eigenvector of ones mean in that case? And why should I calculate the second right eigenvector instead of the of the first right eigenvector in that case? –  Charlie Mar 11 '13 at 17:42
1  
No my matrix is not symmetric, i.e. to go from A to B is not the same than to go from B to A. So it is not double stochastic it is only row stochastic. You can find the reference at that address atlas.media.mit.edu/media/atlas/pdf/… and the eq. is eq. (8) pp 24. Thanks Will! –  Charlie Mar 15 '13 at 9:38
1  
I would recommend adding this information to your original post, and providing any further detail that you can. That may help to generate better responses. If you can find a more technical description of the work by the same authors, that might help too. I've made an attempt at an answer to your question, but I don't believe I've fully addressed your main concern or fully captured the ideas the lie behind the authors' work. If you wish to make use of anything in my post in reformulating your own, feel free. –  Will Orrick Mar 16 '13 at 8:22
show 3 more comments

1 Answer

Consider a row stochastic matrix $T$ whose eigenvalues are all distinct and satisfy $\lvert\lambda_1\rvert>\lvert\lambda_2\rvert>\lvert\lambda_j\rvert,$ $j\ge3.$ It is not necessary to distinguish left from right eigenvalues because left and right eigenvalues are the same. Define the left eigenvectors $u_jT=\lambda_ju_j$ and right eigenvectors $Tv_j=\lambda_jv_j.$ Here the $u_j$ are row vectors and the $v_j$ are column vectors. Left and right eigenvectors corresponding to different eigenvalues are orthogonal. This follows by computing $u_jTv_k$ in two different ways: $$\begin{aligned}(u_jT)v_k&=\lambda_ju_jv_k\\ u_j(Tv_k)&=\lambda_ku_jv_k,\end{aligned}$$ from which one concludes that $(\lambda_j-\lambda_k)u_jv_k=0.$ If $j\ne k,$ then, since the eigenvalues are assumed distinct, $\lambda_j-\lambda_k\ne0$. Hence $u_jv_k=0$. Suppose that it is possible to normalize the $u_j$ and $v_k$ so that the matrices built from the $u_j$ and the $v_k$ are inverses of each other: $$\begin{bmatrix}u_1\\ u_2\\ \vdots\\ u_n\end{bmatrix}\begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}=I=\begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}\begin{bmatrix}u_1\\ u_2\\ \vdots\\ u_n\end{bmatrix}.$$ Subject to the above assumptions, I will describe how one might understand the roles played by $u_1,$ $u_2,$ $v_1,$ and $v_2$ in the situation where $T$ is the transition matrix of a Markov chain. This means that for a stochastic vector $x$ whose elements represent the probabilities of finding the Markov chain in each of its $n$ states, the stochastic vector $xT$ represents the corresponding probabilities after the system has undergone one transition, and $xT^k$ represents the probabilities after the system has undergone $k$ transitions.

If $T$ satisfies certain conditions, which we won't concern ourselves with here, then both $xT^k$ and the rows of $T^k$ will tend toward $u_1$ as $k$ gets large. For this reason, $u_1$ is known as the stable probability vector. Why does this happen? The Perron-Frobenius theorem says that a nonnegative matrix satisfying our conditions has a unique largest eigenvalue, and that the corresponding eigenvector (either left or right) has all positive entries. Moreover, this is the only eigenvector with all positive entries. Since a row stochastic matrix has a right eigenvector with all entries equal to $1$ and eigenvalue $1,$ the largest eigenvalue is $1.$ In other words, $\lambda_1=1$ and $v_1$ is a scalar multiple of the all-ones vector. It is then clear that the corresponding left eigenvector, $u_1$ is unchanged on multiplication by $T,$ that is, we get the stable-vector condition, $u_1T=u_1.$

By our assumptions above, we have $$\begin{bmatrix}u_1\\ u_2\\ \vdots\\ u_n\end{bmatrix}T=\begin{bmatrix}\lambda_1 & 0 & \ldots & 0\\ 0 & \lambda_2 & \ldots & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \ldots & \lambda_n\end{bmatrix}\begin{bmatrix}u_1\\ u_2\\ \vdots\\ u_n\end{bmatrix}$$ and $$T\begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}=\begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}\begin{bmatrix}\lambda_1 & 0 & \ldots & 0\\ 0 & \lambda_2 & \ldots & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \ldots & \lambda_n\end{bmatrix}.$$ Using our assumption on the normalization of $u_j$ and $v_k,$ we obtain $$\begin{bmatrix}u_1\\ u_2\\ \vdots\\ u_n\end{bmatrix}T\,\begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}=\begin{bmatrix}\lambda_1 & 0 & \ldots & 0\\ 0 & \lambda_2 & \ldots & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \ldots & \lambda_n\end{bmatrix}$$ and $$T=\begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}\begin{bmatrix}\lambda_1 & 0 & \ldots & 0\\ 0 & \lambda_2 & \ldots & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \ldots & \lambda_n\end{bmatrix}\begin{bmatrix}u_1\\ u_2\\ \vdots\\ u_n\end{bmatrix}.$$ Hence $$T^k=\begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}\begin{bmatrix}\lambda_1 & 0 & \ldots & 0\\ 0 & \lambda_2 & \ldots & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \ldots & \lambda_n\end{bmatrix}^k\begin{bmatrix}u_1\\ u_2\\ \vdots\\ u_n\end{bmatrix}.$$ Therefore $$T^k=\begin{bmatrix}v_1 & v_2 & \cdots & v_n\end{bmatrix}\begin{bmatrix}\lambda_1^k u_1\\ \lambda_2^k u_2\\ \vdots\\ \lambda_n^k u_n\end{bmatrix}=\lambda_1^kv_1u_1+\lambda_2^kv_2u_2+\ldots+\lambda_n^kv_nu_n.$$ This is a sum of rank-$1$ matrices. By our assumption on the relative magnitudes of the eigenvalues, the second term decays exponentially quickly with respect to the first, and the third and higher terms decay exponentially quickly with respect to the second. Since $\lambda_1=1$ and $v_1$ is the all-ones vector, we have $$T^k=\begin{bmatrix}u_1\\ u_1\\ \vdots\\ u_1\end{bmatrix}+\lambda_2^k\begin{bmatrix}v_{21}u_2\\ v_{22}u_2\\ \vdots\\ v_{2n}u_2\end{bmatrix}+\text{exponentially smaller terms,}$$ where the coefficients $v_{2j}$ are the elements of $v_2.$

Therefore the significance of the first right eigenvector $v_1$ being all ones is that $T^k$ tends toward a matrix with all rows the same and equal to the first left eigenvector $u_1.$ If $\lvert\lambda_2\rvert$ is close to $1,$ then $T^k$ approaches this stable form slowly, whereas if $\lvert\lambda_2\rvert$ is close to $0,$ the stable form is reached quickly. The dominant correction to each row is a multiple of the second left eigenvector $u_2,$ with the relative sizes of the corrections to the $i^\text{th}$ and $j^\text{th}$ rows given by the relative sizes of the $i^\text{th}$ and $j^\text{th}$ elements of the second right eigenvector $v_2.$ I believe this may be what the authors of the article you link to, Atlas of Economic Complexity, page 24, are referring to when they state that $v_2$

is the eigenvector that captures the largest amount of variance in the system and is our measure of economic complexity.

However, I am unsure of the precise meaning of their statement, and have no idea about its economic interpretation; I would welcome clarification or alternative interpretations from anyone reading this. (See Addendum below for my own improvements to the explanation.)

Some remarks on formulating the model in the article as a Markov chain. The model is based on a bipartite graph in which some vertices represent countries and other vertices represent products. There is an edge joining country $c$ and product $p$ if $c$ manufactures $p.$ This graph is described by an adjacency matrix $M$ whose element $M_{cp}$ equals $1$ if $c$ manufactures $p$ and $0$ otherwise. The transitions of the system are the following.

  1. From country vertex $c,$ move to a vertex $p,$ chosen at random from the set of products manufactured by $c$.
  2. From product vertex $p,$ move to a vertex $c,$ chosen at random from the set of countries that manufacture $p.$

Let $s_R$ denote the vector of row sums of $M$ and let $s_C$ denote the vector of column sums of $M$. The elements of $s_R$ and $s_C$ are denoted $k_{c,0}$ and $k_{p,0}$ in the article. Write $S_R=\text{diag}(s_R)$ and $S_C=\text{diag}(s_C).$ These are the diagonal matrices whose diagonal elements are the row and column sums of $M.$ The first type of transition is then described by the transition matrix $S_R^{-1}M$ and the second type by the transition matrix $S_C^{-1}M^T.$

Starting from a country vertex, the system will reach another country vertex after an even number of transitions and will reach a product vertex after an odd number of transitions. A Markov chain on country vertices only can be formulated by means of the transition matrix $$\widetilde{M}=S_R^{-1}MS_C^{-1}M^T$$ in which a transition of the first type is followed by a transition of the second type. Similarly, a Markov chain on product vertices only could be formulated by means of the transition matrix $$S_C^{-1}M^TS_R^{-1}M$$ in which a transition of the second type is followed by a transition of the first type. It is $\widetilde{M}$ that plays the role of $T$ in the definition of the Economic Complexity Index. Similarly, $S_C^{-1}M^TS_R^{-1}M$ plays the role of $T$ in the definition of the Product Complexity Index.

Addendum. Here's a bit of clarification on the limiting process that leads to consideration of the second right eigenvector. Again using the notation $s_R$ for the row-sum vector, the authors are looking at the limiting behavior of $k^{(C)}_{2\ell}:=\widetilde{M}^\ell s_R.$ (The notation $k^{(C)}_{2\ell}$ is mine; elements of this vector are denoted $k_{c,2\ell}$ in the article. Again, the economic interpretation is unclear to me.) As $\ell\rightarrow\infty,$ this approaches a constant vector. But it's not this constant vector that they're interested in; it's how the elements of $k^{(C)}_{2\ell}$ are distributed around their central value. (Again, don't ask me why.) They quantify this by subtracting the mean value of the elements and dividing by the standard deviation: $$\lim_{\ell\rightarrow\infty}\frac{k_{c,2\ell}-\langle k^{(C)}_{2\ell}\rangle}{\text{stddev}(k^{(C)}_{2\ell})}.$$ Returning to the expression for the $\ell^\text{th}$ power of a transition matrix, $$\widetilde{M}^\ell=\begin{bmatrix}u_1\\ u_1\\ \vdots\\ u_1\end{bmatrix}+\lambda_2^\ell\begin{bmatrix}v_{21}u_2\\ v_{22}u_2\\ \vdots\\ v_{2n}u_2\end{bmatrix}+\text{exponentially smaller terms,}$$ we find that $$k_{c,2\ell}=u_1s_R+\lambda_2^\ell v_{2,c}u_2s_R+\ldots.$$ The first term in this expression is constant - it doesn't depend on $c$ - and so it cancels when the mean is subtracted. It also does not contribute to the standard deviation since it amounts to a constant shift of all the elements of the vector. This leaves the second term as the dominant contribution (the only contribution in the $\ell\rightarrow\infty$ limit, since others are exponentially smaller). Furthermore, the quantity $\lambda_2^\ell u_2s_R$ is constant as well, and so cancels when you divide by the standard deviation. This leaves $$\lim_{\ell\rightarrow\infty}\frac{k_{c,2\ell}-\langle k^{(C)}_{2\ell}\rangle}{\text{stddev}(k^{(C)}_{2\ell})}=\frac{v_{2,c}-\langle v_2\rangle}{\text{stddev}(v_2)}.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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