• Aug 16th 2007, 02:05 AM
hasami2
If X=[x1,x2,...,xn]' where x1+x2+...+xn=1.
If A1,A2,...,An are nXn square matrices, all elements are greater than 0 and less than 1.
The sum of all elements of A1 is n. It is also true for A2,...,An.
A1+A2+...+An=E, where E is a matrix of all 1s.

Now we update X by doing followings:

x1(t+1)=X(t)'*A1*X(t)
x2(t+1)=X(t)'*A2*X(t)
...
xn(t+1)=X(t)'*An*X(t)

when t->infinite, what is X?
Thanks.
• Aug 16th 2007, 02:06 AM
hasami2
I do simulations, when t->infinity, X->[1/n, 1/n, ..., 1/n]

but I don't know how to prove it.
• Aug 16th 2007, 07:15 AM
JakeD
Quote:

Originally Posted by hasami2
If X=[x1,x2,...,xn]' where x1+x2+...+xn=1.
If A1,A2,...,An are nXn square matrices, all elements are greater than 0 and less than 1.
The sum of all elements of A1 is n. It is also true for A2,...,An.
A1+A2+...+An=E, where E is a matrix of all 1s.

Now we update X by doing followings:

x1(t+1)=X(t)'*A1*X(t)
x2(t+1)=X(t)'*A2*X(t)
...
xn(t+1)=X(t)'*An*X(t)

when t->infinite, what is X?
Thanks.

Quote:

Originally Posted by hasami2
I do simulations, when t->infinity, X->[1/n, 1/n, ..., 1/n]

but I don't know how to prove it.

I think you can use Banach's fixed point theorem here, although I don't have all the details worked out.

Let the map $\displaystyle T: R^n \to R^n$ be defined by $\displaystyle T(x)_i = x^T A_i x.$

The assumptions on the $\displaystyle A_i$ imply that $\displaystyle \hat{x} = [1/n, \ldots, 1/n]$ satisfies $\displaystyle x = T(x)$, this is, $\displaystyle \hat{x}$ is a fixed point of $\displaystyle T.$ If you can show that $\displaystyle T$ is a contraction mapping, then the fixed point $\displaystyle \hat{x}$ is unique by Banach's theorem and is the limit of the iterative sequence $\displaystyle x^{i+1} = T(x^i).$
• Aug 18th 2007, 08:56 AM
JakeD
Quote:

Originally Posted by hasami2
If X=[x1,x2,...,xn]' where x1+x2+...+xn=1.
If A1,A2,...,An are nXn square matrices, all elements are greater than 0 and less than 1.
The sum of all elements of A1 is n. It is also true for A2,...,An.
A1+A2+...+An=E, where E is a matrix of all 1s.

Now we update X by doing followings:

x1(t+1)=X(t)'*A1*X(t)x2(t+1)=X(t)'*A2*X(t)
...
xn(t+1)=X(t)'*An*X(t)

when t->infinite, what is X?
Thanks.

Quote:

Originally Posted by hasami2
I do simulations, when t->infinity, X->[1/n, 1/n, ..., 1/n]

but I don't know how to prove it.

Quote:

Originally Posted by JakeD
I think you can use Banach's fixed point theorem here, although I don't have all the details worked out.

Let the map $\displaystyle T: R^n \to R^n$ be defined by $\displaystyle T(x)_i = x^T A_i x.$

The assumptions on the $\displaystyle A_i$ imply that $\displaystyle \hat{x} = [1/n, \ldots, 1/n]$ satisfies $\displaystyle x = T(x)$, this is, $\displaystyle \hat{x}$ is a fixed point of $\displaystyle T.$ If you can show that $\displaystyle T$ is a contraction mapping, then the fixed point $\displaystyle \hat{x}$ is unique by Banach's theorem and is the limit of the iterative sequence $\displaystyle x^{i+1} = T(x^i).$

In trying to prove that $\displaystyle T$ is a contraction map, I found that it is not and does not have a unique fixed point.
Take

$\displaystyle A_1 = \begin{bmatrix} .98 & .98 & .01 \\ .98 & .01 & .01 \\ .01 & .01 & .01 \\ \end{bmatrix},$ $\displaystyle A_2 = \begin{bmatrix} .01 & .01 & .98 \\ .01 & .98 & .01 \\ .98 & .01 & .01 \\ \end{bmatrix},$ $\displaystyle A_3 = \begin{bmatrix} .01 & .01 & .01 \\ .01 & .01 & .98 \\ .01 & .98 & .98 \\ \end{bmatrix}.$

Although $\displaystyle [1/3,1/3,1/3]$ is a fixed point of $\displaystyle T$, the sequence $\displaystyle x^{i+1} = T(x^i)$ using the starting vector $\displaystyle x^0 = [1/2,1/2,0]$ converges to $\displaystyle [0.958314,0.030928,0.010758],$ not $\displaystyle [1/3,1/3,1/3].$