stochastic matrix

The examples in this article describe random matrices. Share it with everyone for your reference, the details are as follows:

stochastic matrix

        I have been looking at Google sorting in the past month Core algorithm ---PageRank sorting algorithm [1][2], which involves the description and application of graph theory and Markov chains in many papers [3][4][5] , and the most critical sentence that has always puzzled me is "A stochastic matrix has principal/primary eigenvalue 1"[3][4][5][6][7][8]. Maybe for those who have systematically studied matrix theory, it is very plain and not worth discussing or explaining separately. And here I have to admit my ignorance. Although I have studied some discussions about the properties of matrices in advanced algebra, I have never been exposed to the so-called stochastic matrix (Stochastic Matrix), let alone its properties. So, I tried hard to find relevant literature on the Internet, but the results were not particularly ideal. There was no detailed introduction to random matrices and proof of related properties. I think maybe on the one hand, my search technology is not yet mature, or the search keywords are inaccurate, or there is a lack of information about it on the Internet. Here I would like to take out the relevant information I have collected recently and sort out my ideas for future use. It is also a true record and supervision of my own learning.

Random matrix is ​​actually a type of non-negative matrix (Nonnegative matrix). Non-negative matrix means that the matrix elements are all non-negative (Nonnegative). Of course Non-negative needs to be slightly distinguished from positive matrix (Positive matrix). Non-negative matrices are widely used in computational mathematics, graph theory, linear programming, automatic control and other fields. For their eigenvalues, especially the maximum eigenvalue (note that the maximum here is from the perspective of the module or the concept of absolute value) Maximum) eigenvalue, that is, the estimation of the principal eigenvalue (principal/primary eigenvalue) of the matrix is ​​of great significance [9].

Random matrix is ​​so important, so what kind of matrix is ​​a random matrix? If you are given a non-negative matrix at random, how to determine whether it is a random matrix?

The stochastic matrix should actually be divided into a row stochastic matrix (Row stochastic matrix) and a column stochastic matrix (Column stochastic matrix). A row random matrix is ​​a square matrix whose row sum is equal to 1; a column random matrix is ​​a non-negative matrix whose column sum is equal to 1. Then a non-negative matrix that satisfies the row and column sums of both 1 is a double stochastic matrix (Double stochastic matrix), and the identity matrix is ​​a double stochastic matrix. From a research perspective, in fact, we only need to study the properties of the row matrix. After all, the column random matrix is ​​just the transposed matrix of the row random matrix. Therefore, the following discussion is entirely based on row random matrices.

Since the row sum of random matrix A is 1, then assuming e=(1,1,...,1), then the transposed vector e' of e is an eigenvector of the matrix, corresponding to The eigenvalue of A is 1. In this way, there is still a certain distance to prove that the main eigenvalue of the random matrix is ​​1. Assume that the n eigenvalues ​​of A are λ(i), where i=1,2,...,n; if you want to prove that the property is true, you must prove that |λ(i)|

So I searched for relevant information and posted a message on the "Mathematics PhD Forum" for advice. The reply I got was that I need to prove it. Roughly speaking, I can use the disk theorem. If I want to prove it more accurately, I need to use Perron-Frobenius Theorm[9][10][11][12]. New concepts and methods appear one after another, and it seems that systematic study of numerical methods and numerical calculation theory is required. The information found [10] shows that the spectral radius of any matrix is ​​not greater than any induced matrix norm of the matrix, and the L1-Norm value of the random matrix is ​​1, then the spectral radius (is the main eigenvalue Equivalently speaking) is not greater than 1, and since 1 is an eigenvalue of A, then it is impossible to have an eigenvalue with an absolute value greater than 1: 1 is indeed the main eigenvalue of the random matrix A.

Then the proof of the above properties is equivalent to the conclusion in the proof data [10].

In fact, "the spectral radius of a matrix in any complex field is not greater than any of its induced norms" is just a basic property of matrices. The specific proof is shown in the figure below:

According to the above proof results, it can be seen that for any row random matrix, its spectral radius is 1, that is, the maximum eigenvalue is 1. .

It can be seen that in fact, a small property of the matrix is ​​sometimes a difficult problem for people who have not systematically studied matrix theory. If you want to join the industry, you should understand the rules; if you want to get started, you should be proficient in the trade.

The ratio of the main eigenvalue of the random matrix and the second largest eigenvalue is a basic measure of the convergence speed of the power method. There are many ways to calculate PageRank, and there are countless studies on this. Of course, the most traditional one is to use the power method to determine the PageRank value of each web page crawled into the database. . Due to the huge number of web pages, considering the convergence speed of the power method is not a redundant and useless analysis. The "spectral gap" (Eigengap) of the two eigenvalues ​​is mainly used to measure the stability of the PR value obtained by using the power method. From this point of view, eigenvalue analysis plays a key role in understanding the PageRank algorithm.

Related recommendations:

php version of spiral matrix (from inside to outside)

PHP implements N*M characters Matrix 90 degree rotation

The above is the detailed content of stochastic matrix. For more information, please follow other related articles on the PHP Chinese website!