# Why this algorithm gives an eigenvector?

Suppose I have a square matrix $A$ having the properties:

1) $a_{ij} a_{ji} = 1$

2) $a_{ii}=1$

3) $a_{ij}=a_{ik}a_{kj}$.

If the last condition is not satisfied, then anyway I get a pretty good approximation of an eigenvector using the method below. So the method to obtain an eigenvector of matrix $A$ (with all positive elements, not sure if it works with negative as well):

1) divide every element in a given column by the sum of elements in that column (normalization)

2) calculate average of elements in each row of the matrix obtained in step 1).

Why this method works? Is it only an approximation of an eigenvector? Matrix $A$ can have multiple eigenvectors, so which one am I getting here?

• If you start with a matrix with rational coefficients, then you get a vector with rational coefficients. Yet there are matrices with positive rational coefficients whose eigenvectors do not have rational coefficients, like $\left( \begin{array}{cc} 2 & 1 \\ 1 & 1 \\ \end{array} \right)$ May 10, 2015 at 10:35
• This example shows that there is no finite sequence of steps involving algebraic operations (sum, products, differences, quotients) which starting with the entries of the matrix will produce an eigenvector. May 10, 2015 at 10:41
• @Winther these conditions are apparently meant to hold for all i,j,k. No summation convention.
– daw
May 10, 2015 at 17:23

Apparently I have not understood your process.

$A = \begin{pmatrix} 2 & 1 \\ 3 & 2\end{pmatrix}$ $A' = \begin{pmatrix} 2/5 & 1/3 \\ 3/5 & 2/3\end{pmatrix}$

"eigenvector" $v= \begin{pmatrix} 11/30 \\ 19/30\end{pmatrix}$

But is easy to see that $v$ is not an eigenvector of $A$.

It turns out that you are correct and this method will produce eigenvectors. I'll also show that such a matrix has an eigenvalue equal to $n$ (the dimension of the matrix) and the eigenvector you're calculating is associated with the eigenvalue $n$.

Proof

Let $a_{ij}$ be the elements of our $n \times n$ matrix $A$. The elements of $A'$, the modified matrix, is $$A'_{ij} = \frac{a_{ij}}{\sum_{i=1}^n a_{ij}}$$

And the element of the vector is $$v_i = \sum_{j=1}^n A'_{ij} = \sum_{j=1}^n \frac{a_{ij}}{\sum_{i=1}^n a_{ij}}$$

(Notice that I don't take the average but just the sum because if $v$ is an eigenvector also $\lambda v$ is for every $\lambda$.. so dividing by $n$ here to take the average would be useless)

Now let's calculate $(Av)_i$, the $i$-th element of the vector $Av$. We would like this to be equal to some constant times $v_i$.

$$(Av)_i = \sum_{j=1}^na_{ij}v_j = \sum_{j=1}^na_{ij}\left(\sum_{k=1}^n\frac{a_{jk}}{\sum_{i=1}^na_{ik}}\right)$$

Since $a_{ij}$ does not depend on $k$ I can bring it inside the parenthesis and obtain

$$\sum_{j=1}^n\sum_{k=1}^n\frac{a_{ij}a_{jk}}{\sum_{i=1}^na_{ik}} = \sum_{j=1}^n\sum_{k=1}^n\frac{a_{ik}}{\sum_{i=1}^na_{ik}}$$

Now nothing depends upon $j$ so it simplifies to

$$n\sum_{k=1}^n\frac{a_{ik}}{\sum_{i=1}^na_{ik}} = nv_i$$

So we showed that $$Av = nv$$

so $n$ is an eigenvalue and $v$ one of the corresponding eigenvectors.

Further questions:

It looks like (and it would be nice to prove) that the characteristic polynomial for such a matrix is $P_x(A) = x^n - nx^{n-1}$ Also, is such a matrix diagonalizable?

Maybe I'll try to solve this problems sometime :-)

• OMG, I forgot about the addiitonal properties a square matrix needs to satisfy for it to work. Question edited. May 10, 2015 at 11:36
• Added additional condition. Notice if the 3rd condition isn't satisfied, then anyway we get a good approximation of one of the eigenvectors. May 10, 2015 at 13:35
• @user4205580 What the third condition means? Who is $k$?
– Ant
May 10, 2015 at 13:49
• It means that, for example, $a_{23}$ has to be equal $a_{24}a_{43}$. $k$ is just any number between $1$ and number of rows (columns) of our square matrix $A$. All elements of the matrix need to satisfy this property - no matter what $k$ I choose (between $1$ and number of rows (columns). May 10, 2015 at 14:37
• @user4205580 I think I have showed that indeed your method works. Also, $n$ is an eigenvalue of such a matrix. Tell me what you think :-) By the way, how did you come up with such a construction for $v$? :-)
– Ant
May 10, 2015 at 15:40

First of all $A$ must be a positive matrix, because only the Perron–Frobenius theorem guarantees, that the spectral radius of $A$ is an eigenvalue of $A$.

If $A \in \mathbb{R}^{n \times n}$ is a consitent pairwise comparison matrix, then $A$ is a rank one matrix, because it has one nonzero eigenvalue, which is $n$. Because of that any row or column of $A$ is an eigenvector of $A$, corresponding to $n$, and of course any of their linear combinations are this eigenvector too. Specially the arithmetic mean of the rows is an eigenvector. This eigenvector is called Perron eigenvector, and it is unique within a positive multiplicative constant.

The avarage what you've calculated differs within a positive multiplicative constans from any rows of columns.

If $A$ is not consistent, then $A$ has rank more than one, so this argumentation is false.