Results 1 to 4 of 4

Thread: Quadratic forms

  1. #1
    Newbie
    Joined
    Aug 2007
    Posts
    2

    Quadratic forms

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Aug 2007
    Posts
    2
    I do simulations, when t->infinity, X->[1/n, 1/n, ..., 1/n]

    but I don't know how to prove it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by hasami2 View Post
    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 View Post
    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).$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2006
    Posts
    399
    Awards
    1
    Quote Originally Posted by hasami2 View Post
    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 View Post
    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 View Post
    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].$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic Forms
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 16th 2010, 03:30 AM
  2. quadratic forms
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 4th 2010, 12:48 PM
  3. Binary Quadratic Forms
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Mar 23rd 2010, 05:11 PM
  4. quadratic forms
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 11th 2009, 04:17 PM
  5. Quadratic Forms???
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Mar 3rd 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum