دانشگاه اصفهان نشریه ریاضی و جامعه 2345-6493 8 1 2023 07 10 The convergence of power iteration method for tournament matrices and its applications همگرایی روش تکرار توانی برای ماتریس‌های تورنمنت و کاربردی از آن 35 55 27595 10.22108/msci.2023.136812.1563 FA امیرحسین نخودکار دانشکده علوم ریاضی، دانشگاه کاشان، کاشان، ایران رسول کاظمی دانشکده علوم ریاضی، دانشگاه کاشان، کاشان، ایران Journal Article 2023 02 23 In this paper, we prove that for every tournament matrix with nonzero spectral radius, the power iteration method converges to a nonzero eigenvector corresponding to the eigenvalue with the maximum magnitude. An application of this result for ranking the corresponding players of the matrix is also given. 1. Introduction The power iteration method is a simple numerical method for finding a corresponding eigenvector of a dominant eigenvalue of a matrix, i.e., an eigenvalue with the largest absolute value. Given a matrix $A$, this method starts as the first vector with an initial guess for an eigenvector of a dominant eigenvalue of $A$. For $n>1$, the $n$-th vector in the sequence is obtained by multiplying the $(n-1)$-th vector on the left by $A$. The process continues until either the sequence converges to the desired eigenvector, or it is clear that the sequence is not convergent. The power iteration method is very useful, but it is not convergent in general. A tournament matrix is a square matrix $A$ whose entries are $0$ or $1$ such that $A+A^t=J-I$, where $I$ is the identity matrix and $J$ is a matirx with all entries equal to $1$. In this paper, we show that for every tournament matrix with a nonzero spectral radius, the power iteration method for finding the non-negative eigenvector corresponding to the dominant eigenvalue is convergent. As an application, we will rank the corresponding players of the tournament matrix. 2. Main Resalts The spectral radius of a square matrix $A$ is defined as the maximum absolute value of its eigenvalues and is denoted by $\rho(A)$. Also, for a vector $R=(r_1,\cdots,r_n)\in\mathbb{R}$, we use the notation $\| R\|_1=|r_1|+\cdots+|r_n|$. Theorem 2.1. Let $A$ be a tournament matrix. Then $\rho(A)$ is an eigenvalue of $A$ with the geometric multiplicity one. Moreover, there exists a unique eigenvector $R$ with nonnegative entries sush that $\| R\|_1=1$. Definition 2.2. Let $A$ be a tournamnet matrix. The eigenvalue $R$ in Therorem 2.1 is called the generalized Perron eigenvector of $A$. Definition 2.3. Let $A$ be a tournamnet matrix of order $n$ with $\rho(A)\neq0$. For every positive integer $k$, let \[v_k=\frac{A^kv_{0}}{\| A^kv_{0}\|_1},\] where \[v_0=(\frac{1}{n},\ldots,\frac{1}{n})^t\in\mathbb{R}^n.\] We say that $A$ satisfies the power condition if the sequence $\{v_k\}$ converges to the generalized Perron eigenvector of $A$. Theorem 2.4. Let $A$ be a tournament matrix of order $n$. If $\rho(A)\neq0$, then $A$ satisfies the power condition. Let $A=(a_{ij})$ be a tournament matrix. Then $A$ may be considered as the matrix of a {\it round robin tournamnet}, i.e., a tournament for which every player plays exactly one match against each of the other players. We label the players as $1,2,\cdots,n$. Then $a_{ij}=1$ if and only if player $i$ defeats player $j$. Now, for $X=(1,\cdots,1)^t\in\mathbb{R}^n$, the $i$-th component of the vector $AX$ is the number of wins for player $i$. The product $a_{ij}a_{jk}$ is nonzero if and only if player $i$ defeats player $j$ and player $j$ defeats player $k$. This suggests that player $i$ defeats {\it indirectly} player $j$. The number of such wins can be computed by the vector $A^2X$. Similarly, the product $a_{ij}a_{jk}a_{ks}$ is nonzero exactly when player $i$ defeats player $j$, player $j$ defeats player $k$ and player $k$ defeats player $s$, i.e., again player $i$ defeats indirectly player $j$. Hence, one can count these wins by the matrix $A^3X$. Continuing this argument, we get the vector $(A+A^2+\cdots)X$ which counts all of these direct and indirecet wins. However, this vector may deverge to infinity. To settle this problem, one can normalize the vectors as follows: use the vector \[v_0=\frac{1}{n}X=(\frac{1}{n},\ldots,\frac{1}{n})^t,\] instead of $X$. For every positive number $k$, set \[w_k=\frac{(A+\cdots+A^k)v_0}{\| (A+\cdots+A^k)v_0\|_1}.\] Note taht $\| w_k \|_1=1$ for every nonnegative integer $k$. The following result shows that the sequence $\{w_k\}$ can be used for our ranking problem. Theorem 2.5. Let $A$ be a tournament matrix. If $\rho(A)\neq0$, then the sequence $\{w_k\}$ converges to the generalized Perron eigenvector of $A$. 3. Summary of Proofs Theorem 2.1 follows from [4, (8.3.1)] and [6. (3.1)]. To proof Theorem 2.4, we need some preliminaries as follows: Definition 3.1. A square matrix $P$ is called a {\it permutation matrix} if its rows are obtained by permuting the rows of the identity matrix. Lemma 3.2. A tournament matrix $A$ of order $n$ with $\rho(A)\neq0$ satisfies the power condition if and only if $PAP^t$ satisfies the power condition for every permutation matrix $P$ of order $n$. Proposition 3.3. Let $A$ be a tournament matirx with $\rho(A)\neq0$. If the algebraic multiplicity of $\rho(A)$ is $1$, then $A$ satisfies the power condition. Proposition 3.4. Let $A=\left(\begin{smallmatrix}B&J\\0&C\end{smallmatrix}\right)$ be a tournament matrix of order $n$, where $B$ is a square matirx of nonzero order, $C$ is a nonzero matrix of order $n-m$ and $J$ is an $m\times (n-m)$ matrix whose entries all are $1$. If $\rho(B)=\rho(C)\neq0$ and $B$ and $C$ satisfy the power condition, then so is $A$. Proof of Theorem 2.4. We use induction on the algebraic multiplicity of $\rho(A)$. If the algebraic multiplicity of $\rho(A)$ is $1$ the result follows from Proposition 3.3. Suppose that every tournamnet matrix $T$ with $\rho(T)\neq0$ and the algebraic multiplicity $l$ satisfies the power condition. Assume that the algebraic multiplicity of $\rho(A)$ is $l+1$. Then there exists a permutation matrix $P$ such that $PAP^t$ has a decomposition $PAP^t=\left(\begin{smallmatrix}B&J\\0&C\end{smallmatrix}\right)$ where $B$ is a square matrix of nonzero order $m$ satisfying $\rho(B)=\rho(A)$ with the algebraic multiplicity $1$, $C$ is a square matrix of nonzero order $n-m$ satisfying $\rho(B)=\rho(A)$ with the algebraic multiplicity $l$ and $J$ is an $m\times (n-m)$ matrix whose entries are all $1$. By the hypothesis, $B$ and $C$ satisfy the power condition. Hence, by by Proposition 3.4, $PAP^t$ satisfies the power condition. By Lemma 3.2, the matrix $A$ satisfies the power condition, proving the result. Proof of Theorem 2.5. For a nonnegative number $k$, let $a_k=A^kv_0$, $b_k=\| A^kv_0\|_1$. Since the entries of $A^kv_0$ are nonzero for all $k$, we have \[b_1+\cdots+b_k=\| Av_0\|_1+\cdots+\| A^kv_0\|_1=\| (A+\cdots+A^k)v_0\|_1.\] Hence, \[w_k=\frac{a_1+\cdots+a_k}{b_1+\cdots+b_k}.\] By Theorem 2.4, the sequence $\{\frac{a_k}{b_k}\}$ converges to the generalized Perron vector of $A$. Hence, so does the sequence $\{w_k\}$, thanks to Stolz-Ces\`aro Theorem (see [10, p. 181]). در این مقاله نشان می‌دهیم برای هر ماتریس تورنمنت با شعاع طیفی ناصفر، روش تکرار توانی برای یافتن بردار ویژه‌ی نامنفی متناظر با مقدار ویژه‌ی با بیشترین قدر مطلق، همگراست. کاربردی از این مطلب را نیز برای رده‌بندی بازیکن‌های تورنمنت نظیر ماتریس ارائه می‌دهیم.

https://math-sci.ui.ac.ir/article_27595_51451f085d85cba8c6e3887e2a611b41.pdf