• August 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.
• August 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.
• August 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 $T: R^n \to R^n$ be defined by $T(x)_i = x^T A_i x.$

The assumptions on the $A_i$ imply that $\hat{x} = [1/n, \ldots, 1/n]$ satisfies $x = T(x)$, this is, $\hat{x}$ is a fixed point of $T.$ If you can show that $T$ is a contraction mapping, then the fixed point $\hat{x}$ is unique by Banach's theorem and is the limit of the iterative sequence $x^{i+1} = T(x^i).$
• August 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 $T: R^n \to R^n$ be defined by $T(x)_i = x^T A_i x.$

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

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

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

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