Как найти число фробениуса матрицы

Характеристический полином, собственные числа, собственные векторы матрицы

Характеристический полином

Характеристический полином линейного оператора

определяется как характеристический полином матрицы этого оператора в произвольном базисе линейного пространства, в котором этот оператор задан. Подробнее

☞

ЗДЕСЬ.

Характеристический полином линейного однородного разностного уравнения

$ n_{} $-го порядка
$$
x_{n+K}=a_1 x_{n+K-1}+ dots+ a_n x_K, quad a_n ne 0,
$$
определяется как
$$ lambda^n – a_1 lambda^{n-1} – dots – a_n . $$
Подробнее

☞

ЗДЕСЬ.

Свойства

Теорема Гамильтона-Кэли

Собственное число

Локализация собственных чисел

Локализация вещественных собственных чисел

Симметричная матрица

Произвольная матрица

Собственный вектор

Теорема Перрона-Фробениуса

Методы вычисления характеристического полинома

Метод Леверье

Метод Крылова

Поиск всех собственных чисел

Существуют методы нахождения спектра матрицы, не требующие предварительного построения характеристического полинома.

QR-алгоритм

Частичная проблема собственных чисел

Задачи

Источники

In matrix theory, the Perron–Frobenius theorem, proved by Oskar Perron (1907) and Georg Frobenius (1912), asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding eigenvector can be chosen to have strictly positive components, and also asserts a similar statement for certain classes of nonnegative matrices. This theorem has important applications to probability theory (ergodicity of Markov chains); to the theory of dynamical systems (subshifts of finite type); to economics (Okishio’s theorem,^[1] Hawkins–Simon condition^[2]);
to demography (Leslie population age distribution model);^[3]
to social networks (DeGroot learning process); to Internet search engines (PageRank);^[4] and even to ranking of football
teams.^[5] The first to discuss the ordering of players within tournaments using Perron–Frobenius eigenvectors is Edmund Landau.^[6][7]

Statement[edit]

Let positive and non-negative respectively describe matrices with exclusively positive real numbers as elements and matrices with exclusively non-negative real numbers as elements. The eigenvalues of a real square matrix A are complex numbers that make up the spectrum of the matrix. The exponential growth rate of the matrix powers A^k as k → ∞ is controlled by the eigenvalue of A with the largest absolute value (modulus). The Perron–Frobenius theorem describes the properties of the leading eigenvalue and of the corresponding eigenvectors when A is a non-negative real square matrix. Early results were due to Oskar Perron (1907) and concerned positive matrices. Later, Georg Frobenius (1912) found their extension to certain classes of non-negative matrices.

Positive matrices[edit]

Let be an positive matrix: for . Then the following statements hold.

1. There is a positive real number r, called the Perron root or the Perron–Frobenius eigenvalue (also called the leading eigenvalue or dominant eigenvalue), such that r is an eigenvalue of A and any other eigenvalue λ (possibly complex) in absolute value is strictly smaller than r , |λ| < r. Thus, the spectral radius is equal to r. If the matrix coefficients are algebraic, this implies that the eigenvalue is a Perron number.
2. The Perron–Frobenius eigenvalue is simple: r is a simple root of the characteristic polynomial of A. Consequently, the eigenspace associated to r is one-dimensional. (The same is true for the left eigenspace, i.e., the eigenspace for A^T, the transpose of A.)
3. There exists an eigenvector v = (v₁,…,v_n)^T of A with eigenvalue r such that all components of v are positive: A v = r v, v_i > 0 for 1 ≤ i ≤ n. (Respectively, there exists a positive left eigenvector w : w^T A = r w^T, w_i > 0.) It is known in the literature under many variations as the Perron vector, Perron eigenvector, Perron-Frobenius eigenvector, leading eigenvector, or dominant eigenvector.
4. There are no other positive (moreover non-negative) eigenvectors except positive multiples of v (respectively, left eigenvectors except w), i.e., all other eigenvectors must have at least one negative or non-real component.
5. , where the left and right eigenvectors for A are normalized so that w^Tv = 1. Moreover, the matrix v w^T is the projection onto the eigenspace corresponding to r. This projection is called the Perron projection.
6. Collatz–Wielandt formula: for all non-negative non-zero vectors x, let f(x) be the minimum value of [Ax]_i / x_i taken over all those i such that x_i ≠ 0. Then f is a real valued function whose maximum over all non-negative non-zero vectors x is the Perron–Frobenius eigenvalue.
7. A “Min-max” Collatz–Wielandt formula takes a form similar to the one above: for all strictly positive vectors x, let g(x) be the maximum value of [Ax]_i / x_i taken over i. Then g is a real valued function whose minimum over all strictly positive vectors x is the Perron–Frobenius eigenvalue.
8. Birkhoff–Varga formula: Let x and y be strictly positive vectors. Then ^[8]
9. Donsker–Varadhan–Friedland formula: Let p be a probability vector and x a strictly positive vector. Then ^[9][10]
10. Fiedler formula: ^[11]
11. The Perron–Frobenius eigenvalue satisfies the inequalities

All of these properties extend beyond strictly positive matrices to primitive matrices (see below). Facts 1-7 can be found in Meyer^[12] chapter 8 claims 8.2.11–15 page 667 and exercises 8.2.5,7,9 pages 668–669.

The left and right eigenvectors w and v are sometimes normalized so that the sum of their components is equal to 1; in this case, they are sometimes called stochastic eigenvectors. Often they are normalized so that the right eigenvector v sums to one, while .

Non-negative matrices[edit]

There is an extension to matrices with non-negative entries. Since any non-negative matrix can be obtained as a limit of positive matrices, one obtains the existence of an eigenvector with non-negative components; the corresponding eigenvalue will be non-negative and greater than or equal, in absolute value, to all other eigenvalues.^[13][14] However, for the example , the maximum eigenvalue r = 1 has the same absolute value as the other eigenvalue −1; while for , the maximum eigenvalue is r = 0, which is not a simple root of the characteristic polynomial, and the corresponding eigenvector (1, 0) is not strictly positive.

However, Frobenius found a special subclass of non-negative matrices — irreducible matrices — for which a non-trivial generalization is possible. For such a matrix, although the eigenvalues attaining the maximal absolute value might not be unique, their structure is under control: they have the form , where r is a real strictly positive eigenvalue, and ranges over the complex hth roots of 1 for some positive integer h called the period of the matrix.
The eigenvector corresponding to r has strictly positive components (in contrast with the general case of non-negative matrices, where components are only non-negative). Also all such eigenvalues are simple roots of the characteristic polynomial. Further properties are described below.

Classification of matrices[edit]

Let A be a n × n square matrix over field F.
The matrix A is irreducible if any of the following equivalent properties
holds.

Definition 1 : A does not have non-trivial invariant coordinate subspaces.
Here a non-trivial coordinate subspace means a linear subspace spanned by any proper subset of standard basis vectors of Fⁿ. More explicitly, for any linear subspace spanned by standard basis vectors e_i1 , …,
e_ik, 0 < k < n its image under the action of A is not contained in the same subspace.

Definition 2: A cannot be conjugated into block upper triangular form by a permutation matrix P:

where E and G are non-trivial (i.e. of size greater than zero) square matrices.

Definition 3: One can associate with a matrix A a certain directed graph G_A. It has n vertices labeled 1,…,n, and there is an edge from vertex i to vertex j precisely when a_ij ≠ 0. Then the matrix A is irreducible if and only if its associated graph G_A is strongly connected.

If F is the field of real or complex numbers, then we also have the following condition.

Definition 4: The group representation of on or on given by has no non-trivial invariant coordinate subspaces. (By comparison, this would be an irreducible representation if there were no non-trivial invariant subspaces at all, not only considering coordinate subspaces.)

A matrix is reducible if it is not irreducible.

A real matrix A is primitive if it is non-negative and its mth power is positive for some natural number m (i.e. all entries of A^m are positive).

Let A be real and non-negative. Fix an index i and define the period of index i to be the greatest common divisor of all natural numbers m such that (A^m)_ii > 0. When A is irreducible, the period of every index is the same and is called the period of A. In fact, when A is irreducible, the period can be defined as the greatest common divisor of the lengths of the closed directed paths in G_A (see Kitchens^[15] page 16). The period is also called the index of imprimitivity (Meyer^[12] page 674) or the order of cyclicity. If the period is 1, A is aperiodic. It can be proved that primitive matrices are the same as irreducible aperiodic non-negative matrices.

All statements of the Perron–Frobenius theorem for positive matrices remain true for primitive matrices. The same statements also hold for a non-negative irreducible matrix, except that it may possess several eigenvalues whose absolute value is equal to its spectral radius, so the statements need to be correspondingly modified. In fact the number of such eigenvalues is equal to the period.

Results for non-negative matrices were first obtained by Frobenius in 1912.

Perron–Frobenius theorem for irreducible non-negative matrices[edit]

Let be an irreducible non-negative matrix with period and spectral radius .
Then the following statements hold.

where denotes a zero matrix and the blocks along the main diagonal are square matrices.

• The Perron–Frobenius eigenvalue satisfies the inequalities

The example shows that the (square) zero-matrices along the diagonal may be of different sizes, the blocks A_j need not be square, and h need not divide n.

Further properties[edit]

Let A be an irreducible non-negative matrix, then:

1. (I+A)ⁿ⁻¹ is a positive matrix. (Meyer^[12] claim 8.3.5 p. 672). For a non-negative A, this is also a sufficient condition.^[16]
2. Wielandt’s theorem.^{[17][clarification needed]} If |B|<A, then ρ(B)≤ρ(A). If equality holds (i.e. if μ=ρ(A)e^iφ is eigenvalue for B), then B = e^iφ D AD⁻¹ for some diagonal unitary matrix D (i.e. diagonal elements of D equals to e^iΘ_l, non-diagonal are zero).^[18]
3. If some power A^q is reducible, then it is completely reducible, i.e. for some permutation matrix P, it is true that: , where A_i are irreducible matrices having the same maximal eigenvalue. The number of these matrices d is the greatest common divisor of q and h, where h is period of A.^[19]
4. If c(x) = xⁿ + c_k1 x^n-k₁ + c_k2 x^n-k₂ + … + c_ks x^n-k_s is the characteristic polynomial of A in which only the non-zero terms are listed, then the period of A equals the greatest common divisor of k₁, k₂, … , k_s.^[20]
5. Cesàro averages: where the left and right eigenvectors for A are normalized so that w^Tv = 1. Moreover, the matrix v w^T is the spectral projection corresponding to r, the Perron projection.^[21]
6. Let r be the Perron–Frobenius eigenvalue, then the adjoint matrix for (r–A) is positive.^[22]
7. If A has at least one non-zero diagonal element, then A is primitive.^[23]
8. If 0 ≤ A < B, then r_A ≤ r_B. Moreover, if B is irreducible, then the inequality is strict: r_A < r_B.

A matrix A is primitive provided it is non-negative and A^m is positive for some m, and hence A^k is positive for all k ≥ m. To check primitivity, one needs a bound on how large the minimal such m can be, depending on the size of A:^[24]

• If A is a non-negative primitive matrix of size n, then A^{n2 − 2n + 2} is positive. Moreover, this is the best possible result, since for the matrix M below, the power M^k is not positive for every k < n² − 2n + 2, since (M^{n2 − 2n+1})₁₁ = 0.

Applications[edit]

Numerous books have been written on the subject of non-negative matrices, and Perron–Frobenius theory is invariably a central feature. The following examples given below only scratch the surface of its vast application domain.

Non-negative matrices[edit]

The Perron–Frobenius theorem does not apply directly to non-negative matrices. Nevertheless, any reducible square matrix A may be written in upper-triangular block form (known as the normal form of a reducible matrix)^[25]

PAP⁻¹ =

where P is a permutation matrix and each B_i is a square matrix that is either irreducible or zero. Now if A is
non-negative then so too is each block of PAP⁻¹, moreover the spectrum of A is just the union of the spectra of the
B_i.

The invertibility of A can also be studied. The inverse of PAP⁻¹ (if it exists) must have diagonal blocks of the form B_i⁻¹ so if any
B_i isn’t invertible then neither is PAP⁻¹ or A.
Conversely let D be the block-diagonal matrix corresponding to PAP⁻¹, in other words PAP⁻¹ with the
asterisks zeroised. If each B_i is invertible then so is D and D⁻¹(PAP⁻¹) is equal to the
identity plus a nilpotent matrix. But such a matrix is always invertible (if N^k = 0 the inverse of 1 − N is
1 + N + N² + … + N^k−1) so PAP⁻¹ and A are both invertible.

Therefore, many of the spectral properties of A may be deduced by applying the theorem to the irreducible B_i. For example, the Perron root is the maximum of the ρ(B_i). While there will still be eigenvectors with non-negative components it is quite possible
that none of these will be positive.

Stochastic matrices[edit]

A row (column) stochastic matrix is a square matrix each of whose rows (columns) consists of non-negative real numbers whose sum is unity. The theorem cannot be applied directly to such matrices because they need not be irreducible.

If A is row-stochastic then the column vector with each entry 1 is an eigenvector corresponding to the eigenvalue 1, which is also ρ(A) by the remark above. It might not be the only eigenvalue on the unit circle: and the associated eigenspace can be multi-dimensional. If A is row-stochastic and irreducible then the Perron projection is also row-stochastic and all its rows are equal.

Algebraic graph theory[edit]

The theorem has particular use in algebraic graph theory. The “underlying graph” of a nonnegative n-square matrix is the graph with vertices numbered 1, …, n and arc ij if and only if A_ij ≠ 0. If the underlying graph of such a matrix is strongly connected, then the matrix is irreducible, and thus the theorem applies. In particular, the adjacency matrix of a strongly connected graph is irreducible.^[26][27]

Finite Markov chains[edit]

The theorem has a natural interpretation in the theory of finite Markov chains (where it is the matrix-theoretic equivalent of the convergence of an irreducible finite Markov chain to its stationary distribution, formulated in terms of the transition matrix of the chain; see, for example, the article on the subshift of finite type).

Compact operators[edit]

More generally, it can be extended to the case of non-negative compact operators, which, in many ways, resemble finite-dimensional matrices. These are commonly studied in physics, under the name of transfer operators, or sometimes Ruelle–Perron–Frobenius operators (after David Ruelle). In this case, the leading eigenvalue corresponds to the thermodynamic equilibrium of a dynamical system, and the lesser eigenvalues to the decay modes of a system that is not in equilibrium. Thus, the theory offers a way of discovering the arrow of time in what would otherwise appear to be reversible, deterministic dynamical processes, when examined from the point of view of point-set topology.^[28]

Proof methods[edit]

A common thread in many proofs is the Brouwer fixed point theorem. Another popular method is that of Wielandt (1950). He used the Collatz–Wielandt formula described above to extend and clarify Frobenius’s work.^[29] Another proof is based on the spectral theory^[30] from which part of the arguments are borrowed.

Perron root is strictly maximal eigenvalue for positive (and primitive) matrices[edit]

If A is a positive (or more generally primitive) matrix, then there exists a real positive eigenvalue r (Perron–Frobenius eigenvalue or Perron root), which is strictly greater in absolute value than all other eigenvalues, hence r is the spectral radius of A.

This statement does not hold for general non-negative irreducible matrices, which have h eigenvalues with the same absolute eigenvalue as r, where h is the period of A.

Proof for positive matrices[edit]

Let A be a positive matrix, assume that its spectral radius ρ(A) = 1 (otherwise consider A/ρ(A)). Hence, there exists an eigenvalue λ on the unit circle, and all the other eigenvalues are less or equal 1 in absolute value. Suppose that another eigenvalue λ ≠ 1 also falls on the unit circle. Then there exists a positive integer m such that A^m is a positive matrix and the real part of λ^m is negative. Let ε be half the smallest diagonal entry of A^m and set T = A^m − εI which is yet another positive matrix. Moreover, if Ax = λx then A^mx = λ^mx thus λ^m − ε is an eigenvalue of T. Because of the choice of m this point lies outside the unit disk consequently ρ(T) > 1. On the other hand, all the entries in T are positive and less than or equal to those in A^m so by Gelfand’s formula ρ(T) ≤ ρ(A^m) ≤ ρ(A)^m = 1. This contradiction means that λ=1 and there can be no other eigenvalues on the unit circle.

Absolutely the same arguments can be applied to the case of primitive matrices; we just need to mention the following simple lemma, which clarifies the properties of primitive matrices.

Lemma[edit]

Given a non-negative A, assume there exists m, such that A^m is positive, then A^m+1, A^m+2, A^m+3,… are all positive.

A^m+1 = AA^m, so it can have zero element only if some row of A is entirely zero, but in this case the same row of A^m will be zero.

Applying the same arguments as above for primitive matrices, prove the main claim.

Power method and the positive eigenpair[edit]

For a positive (or more generally irreducible non-negative) matrix A the dominant eigenvector is real and strictly positive (for non-negative A respectively non-negative.)

This can be established using the power method, which states that for a sufficiently generic (in the sense below) matrix A the sequence of vectors b_k+1 = Ab_k / | Ab_k | converges to the eigenvector with the maximum eigenvalue. (The initial vector b₀ can be chosen arbitrarily except for some measure zero set). Starting with a non-negative vector b₀ produces the sequence of non-negative vectors b_k. Hence the limiting vector is also non-negative. By the power method this limiting vector is the dominant eigenvector for A, proving the assertion. The corresponding eigenvalue is non-negative.

The proof requires two additional arguments. First, the power method converges for matrices which do not have several eigenvalues of the same absolute value as the maximal one. The previous section’s argument guarantees this.

Second, to ensure strict positivity of all of the components of the eigenvector for the case of irreducible matrices. This follows from the following fact, which is of independent interest:

Lemma: given a positive (or more generally irreducible non-negative) matrix A and v as any non-negative eigenvector for A, then it is necessarily strictly positive and the corresponding eigenvalue is also strictly positive.

Proof. One of the definitions of irreducibility for non-negative matrices is that for all indexes i,j there exists m, such that (A^m)_ij is strictly positive. Given a non-negative eigenvector v, and that at least one of its components say j-th is strictly positive, the corresponding eigenvalue is strictly positive, indeed, given n such that (Aⁿ)_ii >0, hence: rⁿv_i =
Aⁿv_i ≥
(Aⁿ)_iiv_i
>0. Hence r is strictly positive. The eigenvector is strict positivity. Then given m, such that (A^m)_ij >0, hence: r^mv_j =
(A^mv)_j ≥
(A^m)_ijv_i >0, hence
v_j is strictly positive, i.e., the eigenvector is strictly positive.

Multiplicity one[edit]

This section proves that the Perron–Frobenius eigenvalue is a simple root of the characteristic polynomial of the matrix. Hence the eigenspace associated to Perron–Frobenius eigenvalue r is one-dimensional. The arguments here are close to those in Meyer.^[12]

Given a strictly positive eigenvector v corresponding to r and another eigenvector w with the same eigenvalue. (The vectors v and w can be chosen to be real, because A and r are both real, so the null space of A-r has a basis consisting of real vectors.) Assuming at least one of the components of w is positive (otherwise multiply w by −1). Given maximal possible α such that u=v- α w is non-negative, then one of the components of u is zero, otherwise α is not maximum. Vector u is an eigenvector. It is non-negative, hence by the lemma described in the previous section non-negativity implies strict positivity for any eigenvector. On the other hand, as above at least one component of u is zero. The contradiction implies that w does not exist.

Case: There are no Jordan cells corresponding to the Perron–Frobenius eigenvalue r and all other eigenvalues which have the same absolute value.

If there is a Jordan cell, then the infinity norm
(A/r)^k_∞ tends to infinity for k → ∞ ,
but that contradicts the existence of the positive eigenvector.

Given r = 1, or A/r. Letting v be a Perron–Frobenius strictly positive eigenvector, so Av=v, then:

So A^k_∞ is bounded for all k. This gives another proof that there are no eigenvalues which have greater absolute value than Perron–Frobenius one. It also contradicts the existence of the Jordan cell for any eigenvalue which has absolute value equal to 1 (in particular for the Perron–Frobenius one), because existence of the Jordan cell implies that A^k_∞ is unbounded. For a two by two matrix:

hence J^k_∞ = |k + λ| (for |λ| = 1), so it tends to infinity when k does so. Since J^k = C⁻¹ A^kC, then A^k ≥ J^k/ (C⁻¹ C ), so it also tends to infinity. The resulting contradiction implies that there are no Jordan cells for the corresponding eigenvalues.

Combining the two claims above reveals that the Perron–Frobenius eigenvalue r is simple root of the characteristic polynomial. In the case of nonprimitive matrices, there exist other eigenvalues which have the same absolute value as r. The same claim is true for them, but requires more work.

No other non-negative eigenvectors[edit]

Given positive (or more generally irreducible non-negative matrix) A, the Perron–Frobenius eigenvector is the only (up to multiplication by constant) non-negative eigenvector for A.

Other eigenvectors must contain negative or complex components since eigenvectors for different eigenvalues are orthogonal in some sense, but two positive eigenvectors cannot be orthogonal, so they must correspond to the same eigenvalue, but the eigenspace for the Perron–Frobenius is one-dimensional.

Assuming there exists an eigenpair (λ, y) for A, such that vector y is positive, and given (r, x), where x – is the left Perron–Frobenius eigenvector for A (i.e. eigenvector for A^T), then
rx^Ty = (x^T A) y = x^T (Ay) = λx^Ty, also x^T y > 0, so one has: r = λ. Since the eigenspace for the Perron–Frobenius eigenvalue r is one-dimensional, non-negative eigenvector y is a multiple of the Perron–Frobenius one.^[31]

Collatz–Wielandt formula[edit]

Given a positive (or more generally irreducible non-negative matrix) A, one defines
the function f on the set of all non-negative non-zero vectors x such that f(x) is the minimum value of [Ax]_i / x_i taken over all those i such that x_i ≠ 0. Then f is a real-valued function, whose maximum is the Perron–Frobenius eigenvalue r.

For the proof we denote the maximum of f by the value R. The proof requires to show R = r. Inserting the Perron-Frobenius eigenvector v into f, we obtain f(v) = r and conclude r ≤ R. For the opposite inequality, we consider an arbitrary nonnegative vector x and let ξ=f(x). The definition of f gives 0 ≤ ξx ≤ Ax (componentwise). Now, we use the positive right eigenvector w for A for the Perron-Frobenius eigenvalue r, then ξ w^T x = w^T ξx ≤ w^T (Ax) = (w^T A)x = r w^T x . Hence f(x) = ξ ≤ r, which implies
R ≤ r.^[32]

Perron projection as a limit: A^k/r^k[edit]

Let A be a positive (or more generally, primitive) matrix, and let r be its Perron–Frobenius eigenvalue.

1. There exists a limit A^k/r^k for k → ∞, denote it by P.
2. P is a projection operator: P² = P, which commutes with A: AP = PA.
3. The image of P is one-dimensional and spanned by the Perron–Frobenius eigenvector v (respectively for P^T—by the Perron–Frobenius eigenvector w for A^T).
4. P = vw^T, where v,w are normalized such that w^T v = 1.
5. Hence P is a positive operator.

Hence P is a spectral projection for the Perron–Frobenius eigenvalue r, and is called the Perron projection. The above assertion is not true for general non-negative irreducible matrices.

Actually the claims above (except claim 5) are valid for any matrix M such that there exists an eigenvalue r which is strictly greater than the other eigenvalues in absolute value and is the simple root of the characteristic polynomial. (These requirements hold for primitive matrices as above).

Given that M is diagonalizable, M is conjugate to a diagonal matrix with eigenvalues r₁, … , r_n on the diagonal (denote r₁ = r). The matrix M^k/r^k will be conjugate (1, (r₂/r)^k, … , (r_n/r)^k), which tends to (1,0,0,…,0), for k → ∞, so the limit exists. The same method works for general M (without assuming that M is diagonalizable).

The projection and commutativity properties are elementary corollaries of the definition: MM^k/r^k = M^k/r^k M ; P² = lim M^2k/r^2k = P. The third fact is also elementary: M(Pu) = M lim M^k/r^k u = lim rM^k+1/r^k+1u, so taking the limit yields M(Pu) = r(Pu), so image of P lies in the r-eigenspace for M, which is one-dimensional by the assumptions.

Denoting by v, r-eigenvector for M (by w for M^T). Columns of P are multiples of v, because the image of P is spanned by it. Respectively, rows of w. So P takes a form (a v w^T), for some a. Hence its trace equals to (a w^T v). Trace of projector equals the dimension of its image. It was proved before that it is not more than one-dimensional. From the definition one sees that P acts identically on the r-eigenvector for M. So it is one-dimensional. So choosing (w^Tv) = 1, implies P = vw^T.

Inequalities for Perron–Frobenius eigenvalue[edit]

For any non-negative matrix A its Perron–Frobenius eigenvalue r satisfies the inequality:

This is not specific to non-negative matrices: for any matrix A with an eigenvalue it is true
that . This is an immediate corollary of the
Gershgorin circle theorem. However another proof is more direct:

Any matrix induced norm satisfies the inequality for any eigenvalue because, if is a corresponding eigenvector, . The infinity norm of a matrix is the maximum of row sums: Hence the desired inequality is exactly applied to the non-negative matrix A.

Another inequality is:

This fact is specific to non-negative matrices; for general matrices there is nothing similar. Given that A is positive (not just non-negative), then there exists a positive eigenvector w such that Aw = rw and the smallest component of w (say w_i) is 1. Then r = (Aw)_i ≥ the sum of the numbers in row i of A. Thus the minimum row sum gives a lower bound for r and this observation can be extended to all non-negative matrices by continuity.

Another way to argue it is via the Collatz-Wielandt formula. One takes the vector x = (1, 1, …, 1) and immediately obtains the inequality.

Further proofs[edit]

Perron projection[edit]

The proof now proceeds using spectral decomposition. The trick here is to split the Perron root from the other eigenvalues. The spectral projection associated with the Perron root is called the Perron projection and it enjoys the following property:

The Perron projection of an irreducible non-negative square matrix is a positive matrix.

Perron’s findings and also (1)–(5) of the theorem are corollaries of this result. The key point is that a positive projection always has rank one. This means that if A is an irreducible non-negative square matrix then the algebraic and geometric multiplicities of its Perron root are both one. Also if P is its Perron projection then AP = PA = ρ(A)P so every column of P is a positive right eigenvector of A and every row is a positive left eigenvector. Moreover, if Ax = λx then PAx = λPx = ρ(A)Px which means Px = 0 if λ ≠ ρ(A). Thus the only positive eigenvectors are those associated with ρ(A). If A is a primitive matrix with ρ(A) = 1 then it can be decomposed as P ⊕ (1 − P)A so that Aⁿ = P + (1 − P)Aⁿ. As n increases the second of these terms decays to zero leaving P as the limit of Aⁿ as n → ∞.

The power method is a convenient way to compute the Perron projection of a primitive matrix. If v and w are the positive row and column vectors that it generates then the Perron projection is just wv/vw. The spectral projections aren’t neatly blocked as in the Jordan form. Here they are overlaid and each generally has complex entries extending to all four corners of the square matrix. Nevertheless, they retain their mutual orthogonality which is what facilitates the decomposition.

Peripheral projection[edit]

The analysis when A is irreducible and non-negative is broadly similar. The Perron projection is still positive but there may now be other eigenvalues of modulus ρ(A) that negate use of the power method and prevent the powers of (1 − P)A decaying as in the primitive case whenever ρ(A) = 1. So we consider the peripheral projection, which is the spectral projection of A corresponding to all the eigenvalues that have modulus ρ(A). It may then be shown that the peripheral projection of an irreducible non-negative square matrix is a non-negative matrix with a positive diagonal.

Cyclicity[edit]

Suppose in addition that ρ(A) = 1 and A has h eigenvalues on the unit circle. If P is the peripheral projection then the matrix R = AP = PA is non-negative and irreducible, R^h = P, and the cyclic group P, R, R², …., R^h−1 represents the harmonics of A. The spectral projection of A at the eigenvalue λ on the unit circle is given by the formula . All of these projections (including the Perron projection) have the same positive diagonal, moreover choosing any one of them and then taking the modulus of every entry invariably yields the Perron projection. Some donkey work is still needed in order to establish the cyclic properties (6)–(8) but it’s essentially just a matter of turning the handle. The spectral decomposition of A is given by A = R ⊕ (1 − P)A so the difference between Aⁿ and Rⁿ is Aⁿ − Rⁿ = (1 − P)Aⁿ representing the transients of Aⁿ which eventually decay to zero. P may be computed as the limit of A^nh as n → ∞.

Counterexamples[edit]

The matrices L = , P = , T = , M = provide simple examples of what can go wrong if the necessary conditions are not met. It is easily seen that the Perron and peripheral projections of L are both equal to P, thus when the original matrix is reducible the projections may lose non-negativity and there is no chance of expressing them as limits of its powers. The matrix T is an example of a primitive matrix with zero diagonal. If the diagonal of an irreducible non-negative square matrix is non-zero then the matrix must be primitive but this example demonstrates that the converse is false. M is an example of a matrix with several missing spectral teeth. If ω = e^iπ/3 then ω⁶ = 1 and the eigenvalues of M are {1,ω²,ω³=-1,ω⁴} with a dimension 2 eigenspace for +1 so ω and ω⁵ are both absent. More precisely, since M is block-diagonal cyclic, then the eigenvalues are {1,-1} for the first block, and {1,ω²,ω⁴} for the lower one^{[citation needed]}

Terminology[edit]

A problem that causes confusion is a lack of standardisation in the definitions. For example, some authors use the terms strictly positive and positive to mean > 0 and ≥ 0 respectively. In this article positive means > 0 and non-negative means ≥ 0. Another vexed area concerns decomposability and reducibility: irreducible is an overloaded term. For avoidance of doubt a non-zero non-negative square matrix A such that 1 + A is primitive is sometimes said to be connected. Then irreducible non-negative square matrices and connected matrices are synonymous.^[33]

The nonnegative eigenvector is often normalized so that the sum of its components is equal to unity; in this case, the eigenvector is the vector of a probability distribution and is sometimes called a stochastic eigenvector.

Perron–Frobenius eigenvalue and dominant eigenvalue are alternative names for the Perron root. Spectral projections are also known as spectral projectors and spectral idempotents. The period is sometimes referred to as the index of imprimitivity or the order of cyclicity.

See also[edit]

• Min-max theorem
• Z-matrix (mathematics)
• M-matrix
• P-matrix
• Hurwitz matrix
• Metzler matrix (Quasipositive matrix)
• Positive operator
• Krein–Rutman theorem

Notes[edit]

References[edit]

• Perron, Oskar (1907), “Zur Theorie der Matrices”, Mathematische Annalen, 64 (2): 248–263, doi:10.1007/BF01449896, hdl:10338.dmlcz/104432, S2CID 123460172
• Frobenius, Georg (May 1912), “Ueber Matrizen aus nicht negativen Elementen”, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: 456–477
• Frobenius, Georg (1908), “Über Matrizen aus positiven Elementen, 1”, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: 471–476
• Frobenius, Georg (1909), “Über Matrizen aus positiven Elementen, 2”, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: 514–518
• Gantmacher, Felix (2000) [1959], The Theory of Matrices, Volume 2, AMS Chelsea Publishing, ISBN 978-0-8218-2664-5 (1959 edition had different title: “Applications of the theory of matrices”. Also the numeration of chapters is different in the two editions.)
• Langville, Amy; Meyer, Carl (2006), Google page rank and beyond, Princeton University Press, doi:10.1007/s10791-008-9063-y, ISBN 978-0-691-12202-1, S2CID 7646929
• Keener, James (1993), “The Perron–Frobenius theorem and the ranking of football teams”, SIAM Review, 35 (1): 80–93, doi:10.1137/1035004, JSTOR 2132526
• Meyer, Carl (2000), Matrix analysis and applied linear algebra (PDF), SIAM, ISBN 978-0-89871-454-8, archived from the original (PDF) on 2010-03-07
• Minc, Henryk (1988), Nonnegative matrices, John Wiley&Sons,New York, ISBN 0-471-83966-3
• Romanovsky, V. (1933), “Sur les zéros des matrices stocastiques”, Bulletin de la Société Mathématique de France, 61: 213–219, doi:10.24033/bsmf.1206
• Collatz, Lothar (1942), “Einschließungssatz für die charakteristischen Zahlen von Matrizen”, Mathematische Zeitschrift, 48 (1): 221–226, doi:10.1007/BF01180013, S2CID 120958677
• Wielandt, Helmut (1950), “Unzerlegbare, nicht negative Matrizen”, Mathematische Zeitschrift, 52 (1): 642–648, doi:10.1007/BF02230720, hdl:10338.dmlcz/100322, S2CID 122189604

Further reading[edit]

• Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. ISBN 0-89871-321-8.
• Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer, 2001.
• A. Graham, Nonnegative Matrices and Applicable Topics in Linear Algebra, John Wiley&Sons, New York, 1987.
• R. A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 1990
• Bas Lemmens and Roger Nussbaum, Nonlinear Perron-Frobenius Theory, Cambridge Tracts in Mathematics 189, Cambridge Univ. Press, 2012.
• S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability London: Springer-Verlag, 1993. ISBN 0-387-19832-6 (2nd edition, Cambridge University Press, 2009)
• Seneta, E. Non-negative matrices and Markov chains. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973) ISBN 978-0-387-29765-1
• Suprunenko, D.A. (2001) [1994], “Perron–Frobenius theorem”, Encyclopedia of Mathematics, EMS Press (The claim that A_j has order n/h at the end of the statement of the theorem is incorrect.)
• Varga, Richard S. (2002), Matrix Iterative Analysis (2nd ed.), Springer-Verlag.

Для любой неотрицательной матрицы А=>0
существует собственное значение λ_А=>0
(называемое числом Фробениуса) такое,
что λ_А=>|λ| для любого собственного
значения λ матрицы А. Кроме того,
существует неотрицательный собственный
вектор
_А=>0,
соответствующий собственному значению
λ_А и называемый вектором Фробениуса.
Причём, если А>0, то λ_А>0 и
_А>0

2. Докажите следующее утверждение: если
>0
– собственный вектор неотрицательной
матрицы, то он является ее вектором
Фробениуса.

Обозначим через α собственное значение,
которому принадлежит вектор
,
следовательно, выполнено равенство
A=α
Умножая его слева на
^T_A
и учитывая, что
^T_AA=_A^T_A,
имеем:
^T_AA=_A^T_A
так что,
^T_A=_A^T_A.
Поскольку по условию>0,
то
^T_A
0,
так что α= λ_А, ч.т.д.

3. Докажите следующее утверждение. Пусть s и s – минимальная и максимальная суммы элементов столбцов матрицы а. Тогда число Фробениуса λА матрицы а удовлетворяет неравенству s

Док-во: выберем в качестве вектора
Фробениуса

вектор, сумма координат которого равна
1, т.е.
^TA
= 1

По определению имеем AA=λAA
Умножая это равенство слева на
^T
и учитывая, что
=^TA,
получим
A
= λ_А(^TA),
поэтому λ_А =A
= s₁x₁+s₂x₂+…+s_nx_n
отсюда следует, что s(x₁+…+x_n)_AS(x₁+…x_n).
Учитывая, что сумма координат вектора
x_A
равна 1, из неравенства получаем s

4. Запишите структурную таблицу и
уравнение межотраслевого баланса
Леонтьева для трехотраслевой модели
экономики; укажите экономический смысл
входящих в уравнение величин. Запишите
формулу вычисления элементов матрицы
Л. Через известные эл-ты струт. Табл.
Межотр. Баланса.

Произв. Потребление	Конечное потребление	Валовой выпуск
X11 X12 … X1n	Y1	X1
X21 X22 … X2n	Y2	X2
…	…	…
X1n Xn2 … Xnn	Yn	Xn

– уравнение межотраслевого баланса
(уравнение Леонтьева). Межотраслевой
баланс — экономико-математическая
балансовая модель, характеризующая
межотраслевые производственные
взаимосвязи в экономике страны. Основная
задача межотраслевого баланса состоит
в нахождении такого вектора валового
выпуска
,
который при известной матрице прямых
затрат A обеспечивает заданный вектор
конечного продукта
.
Зная матрицу А и вектор

остаётся решить уравнение
.

5. Сформулируйте и докажите первый критерий продуктивности

Матрица А=>0 продуктивна тогда и только
тогда, когда матрица
существует
и неотрицательна. Пусть существует
=>0,
тогда x=(E-A)^-1y,
где оба множителя >0, следовательно,
x=>0, значит матрица
продуктивна. Пусть А продуктивна.
(E-A)x=e₁,
значит с₁=>0, (E-A)x=e₂,
значит с₂=>0, следовательно,
(с₁,с₂,c_n)=C=>0.
(E-A)C=E=>C=(E-A)^-1=>0

6. Докажите, что если неотрицательная квадратная матрица продуктивна, то ее число Фробениуса меньше 1

Матрица А≥0 называется продуктивной,
если для любого вектора
≥0
существует решение
≥0
уравнения

Пусть матрица А – неотрицательна и
продуктивна.

Тогда для любого неотрицательного
вектора

существует решение
≥0
уравнения

Пусть
>0,
тогда, очевидно,
>0.
Умножив

слева еа левый вектор Фробениуса

и учитывая, что

A=,
то получим

>0,
>0,
то
>0,

>0. Поэтому из последнего равенства
вытекает, что

<1.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Category:

• Наука
• Cancel

Норма Фробениуса

Норма Фробениуса или, как её ещё называют Евклидова норма, — это квадратный корень сумм квадратов модулей элементов матрицы размера m × n:

Простой пример. Есть матрица размера 3 × 3:

Она же, но с элементами, возведёнными в квадрат:

Сумма элементов этой матрицы будет равна 60. Квадратный корень из 60 примерно равен 7,746. Это число и есть норма Фробениуса для нашей матрицы.

Есть иной способ вычисления нормы Фробениуса: как квадратный корень произведения следа этой матрицы и эрмитово-сопряжённой матрицы:

https://ru.wikipedia.org/wiki/Норма_матрицы#Норма_Фробениуса

8.2 Утверждение

Пусть positiveи в качестве неотрицательный соответственно описывают матрицы исключительно положительными действительными числами в элементах и ​​матриц. с исключительно неотрицательными действительными числами в качестве элементов. собственные значения реальная квадратная матрица A – это комплексные числа, которые составляют спектр. экспоненциальный рост степеней матрицы A при k → ∞ управляется значение A с наибольшим абсолютным значением (модулем ). Теорема неотъемлемых свойств главного значения и соответствующих собственных векторов, когда A –рицательная вещественная квадратная матрица. Первые результаты были связаны с Оскаром Перроном (1907) и касались положительных матриц. Позже Георг Фробениус (1912) нашел их распространение на классы неотрицательных матриц.

Положительные матрицы

Пусть A = (aij) { displaystyle A = (a_ {ij})}будет n × n { displaystyle n times n}положительная матрица: aij>0 { displaystyle a_ {ij}>0}для 1 ≤ i, j ≤ n { displaystyle 1 leq i, j leq n}. Тогда справедливы следующие утверждения.

1. Существует положительное действительное число r, называемое корнем Перрона или собственным уровнем Перрона – Фробениуса (также называется ведущим величиной положения или доминантным определенным значением ), так что r области значения A и любого другого значения длины λ (возможно, комплексным ) в абсолютное значение строго меньше, чем r, | λ | спектральный радиус ρ (A) { displaystyle rho (A)}равно г. Если матричные коэффициенты являются алгебраическими, это означает, что собственное значение – это Перронное число.
2. Собственное значение Перрона – Фробениуса простое: r является основным корнем типического многочлена от A. Следовательно, собственное подпространство, связанное с r, одномерно. (То же самое верно для левого собственного подпространства, т. Е. Собственного подпространства для A, транспонированной A.)
3. Существует собственное v = (v 1,…, v n) оператора A с числом r таким, что все компоненты v положительны: A v = rv, v i>0 для 1 ≤ i ≤ n. (Соответственно, существует положительный левый собственный вектор w: w A = rw, w i>0.) Он известен в литературе во многих вариантах как Вектор Перрона, Собственный вектор Перрона, Собственный вектор Перрона-Фробениуса, ведущий собственный вектор или доминантный собственный вектор .
4. Других положительных (тем более неотрицательных) собственных векторов, кроме положительных, нет кратные v (соответственно, левые собственные конструкции, кроме w), т. е. все остальные конструктивные элементы должны иметь хотя бы один отрицательный компонент.
5. lim k → ∞ A k / rk = vw T { displaystyle lim _ {k rightarrow infty} A ^ {k} / r ^ {k} = vw ^ {T}}, где левый и правый собственный дизайн для A нормированы так, что wv = 1. Кроме того, матрица vw – это проекция на собственное подпространство, соответствующее r. Эта проекция называется проекцией Перрона .
6. Формула Коллатца –Виландта : для всех неотрицательных ненулевых векторов x пусть f (x) будет минимальным размером [Ax] i / x i, взятый по всем тем i таким, что x i ≠ 0. Тогда f вещественная функция, максимум по всем не -отрицательные ненулевые стандарты x надлежащего уровня Перрона – Фробениуса.
7. Формула «Min-max» Коллатца – Виландта принимает форму, аналогичную приведенной выше: для всех строго положительных векторов x пусть g (x) – максимальное значение [Ax] i / x i, взятое по i. Тогда g – вещественная функция, минимум которой по всем строго положительным вещественным веществом x является собственное Перрона – Фробениуса.
8. Формула Биркгофа – Варга : Пусть x и y – строго положительные рекомендации. Тогда r = sup x>0 inf y>0 y ⊤ A xy ⊤ x = inf x>0 sup y>0 y ⊤ A xy ⊤ x = inf x>0 sup y>0 ∑ i, j = 1 nxi A ijyj / ∑ i = 1 nyixi. { displaystyle r = sup _ {x>0} inf _ {y>0} { frac {y ^ { top} Ax} {y ^ { top} x}} = inf _ {x>0} sup _ {y>0} { frac {y ^ { top} Ax} {y ^ { top} x}} = inf _ {x>0} sup _ {y>0} sum _ {i, j = 1} ^ {n} x_ {i} A_ {ij} y_ {j} / sum _ {i = 1} ^ {n} y_ {i} x_ {i}.}
9. Донскер – Варадхан – Тогда Варадхан – <>Формула Фридланда : Пусть p – вектор вероятности, а x – строго положительный вектор. r = sup p inf x>0 ∑ i = 1 npi [A x ] i / xi. { Displaystyle r = sup _ {p} inf _ {x>0} sum _ {i = 1} ^ {n} p_ {i} [Ax] _ {i} / x_ { i}.}
10. Формула Фидлера : r = sup z>0 inf x>0, y>0, x ∘ y = zy ⊤ A xy ⊤ x = sup z>0 inf x>0, y>0, x ∘ y = z ∑ i, j = 1 nxi A ijyj / ∑ i = 1 nyixi. { Displaystyle г = sup _ {z>0} inf _ {x>0, y>0, x circ y = z} { frac {y ^ { top} Ax} {y ^ { top} x}} = sup _ {z>0} inf _ {x>0, y>0, x circ y = z} sum _ {i, j = 1} ^ { n} x_ {i} A_ {ij} y_ {j} / sum _ {i = 1} ^ {n} y_ {i} x_ {i}.}
11. Собственное значение Перрона – Фробениуса удовлетворяет неравенствам

min i ∑ jaij ≤ r ≤ max i ∑ jaij. { displaystyle} j min _ sum. { displaystyle} j min _ sum. } a_ {ij} leq r leq max _ {i} sum _ {j} a_ {ij}.}

Все эти свойства выходят за рамки строго положительных матриц до примитивных матриц ( см. Ниже). Факты 1-7 можно найт и в Мейере глава 8 утверждает 8.2.11–15 стр. 667 и упражнениях 8.2.5,7,9 стр. 668–669.

Левый и правый построенный w и v таковы, что времена нормированы так, чтобы сумма их компонентов была равна 1; в этом случае их иногда называют стохастическими собственными руками . Как w T v = 1 { displaystyle w ^ {T} v = 1}.

неотрицательные матрицы

Имеется расширение матриц. с неотрицательными элементами. Так как любая неотрицательная матрица может быть получена как предел положительных матриц, получается существование собственного вектора с неотрицательными компонентами; соответствующее собственное значение будет неотрицательным и больше или равно по модулю всем остальным собственным значениям. Однако для <пример294>A = (0 1 1 0) { displaystyle A = left ({ begin {smallmatrix} 0 1 \ 1 0 end {smallmatrix}} right)}максимальное собственное значение r = 1 имеет то же абсолютное значение, что и другое собственное значение -1; а для A = (0 1 0 0) { displaystyle A = left ({ begin {smallmatrix} 0 1 \ 0 0 end {smallmatrix}} right)}, максимальное собственное значение r = 0, не является основным корнем характеристического полинома, и соответствующий собственный вектор (1, 0) не является строго положительным.

Однако Фробениус обнаружил особый подкласс неотрицательных матриц – неприводимых матриц, возможно нетривиальное обобщение. Для таких матрицы, хотя собственные значения, достигают абсолютного значения, их структура находится под контролем: они имеют вид ω r { displaystyle omega r}, где r – действительное строго положительное собственное значение, а ω { displaystyle omega}проходит через комплексные корни hth из 1 для некоторого положительного целого числа h, называемого периодом матрицы. Собственный вектор, соответствующий, имеет строго положительные компоненты (отличие от общего случая неотрицательных матриц, где компоненты только неотрицательны). Также все такие собственные значения являются простыми корнями характеристического многочлена. Другие свойства предложения ниже.

Классификация матриц

Пусть A – квадратная матрица (не обязательно положительная или даже действительная). Матрица A неприводима, выполняется любое из следующих эквивалентных свойств.

Определение 1: A не имеет нетривиальных инвариантных координатных подпространств. Здесь нетривиальное координатное подпространство означает линейное подпространство , натянутое на любое собственное подмножество базисных векторов R n { displaystyle mathbb {R} ^ {n}}. Более точно, для любого линейного подпространства, натянутого на стандартные базисные стандарты e i1,…, e ik, 0 < k < n its image under the action of A is not contained in the same subspace.

Эквивалентно, представление группы из (R, +) { displaystyle ( mathbb {R}, +)}на R n { displaystyle mathbb {R} ^ {n}}задано t ↦ exp ⁡ (t A) { displaystyle t mapsto exp (tA)}не имеет нетривиальных инвариантных координатных подпространств. (Для сравнения, это было бы неприводимым представлением, если бы вообще не было нетривиальных инвариантных подпространств, не только с учетом координатных подпространств.)

Определение 2: Не может быть сопряжен в блок верхняя треугольная форма с помощью матрицы перестановок P:

PAP – 1 ≠ (EF 0 G), { displaystyle PAP ^ {- 1} neq { begin {pmatrix} EF \ 0 G end {pmatrix}},}

где E и G – нетривиальные (т.е. размером больше нуля) квадратные матрицы.

Если A неотрицательно, имеет другое определение:

Определение 3: Можно связать с матрицей A некий ориентированный граф GA. Он имеет ровно n вершин, где n – размер A, и есть ребро от вершины i до вершины j именно тогда, когда A ij>0. Тогда матрица A неприводима тогда и только тогда, когда связанная с ней граф G A является Матрица приводима, если она не является неприводимой.

Матрица A является примитивной, если она неотрицательна и ее степень m положительна для некоторого натурального числа m (т.е. все элементы матрицы A положительны).

Пусть А неотрицательно. Зафиксируйте индекс i и определите период индекс i как наибольший общий делитель всех натуральных чисел m, что (A) ii>0. Когда A неприводима, каждый период одинаков и называется периодом A. Фактически, когда A неприводимо, период может быть определен как наибольший общий делитель замкнутые границы пути в G A (см. Кухни) на стр. 16). Период также называется индексом импримитивности (стр. 674 Мейера) или порядком цикличности. Если период равен 1, A является апериодическим . Можно доказать, что примитивные матрицы – это то же самое, что и неприводимые апериодические неотрицательные матрицы.

Все утверждение теоремы Перрона – Фробениуса для положительных матриц остаются верными для примитивных матриц. Те же справедливы и для неотрицательной неприводимой матрицы, за исключением того, что она может иметь несколько значений. Фактически количество таких значений равно периоду.

Результаты для неотрицательных матриц были впервые получены Фробениусом в 1912 году.

Теорема Перрона – Фробениуса для неприводимых неотрицательных матриц

Пусть A – неприводимая неотрицательная матрица. Матрица размера n × n с периодом h и спектральным радиусом ρ (A) = r. Тогда верны следующие утверждения.

1. Число r – положительное действительное и собственное значение матрицы A, называемое собственное число Перрона – Фробениуса .
2. Собственное значение Перрона – Фробениуса r простое. Правое и левое собственные подпространства, связанные с r, одномерны.
3. A имеет правый собственный вектор v с соответствующим значением r, все компоненты которого положительны.
4. Аналогично, A левый собственный вектор с собственным значением r, все компоненты которого положительны.
5. Единственные собственные компоненты положительны, связанные с определением r.
6. Матрица A имеет ровно h (где h – период ) комплексные собственные значения с модулем r. Каждый из них является основным корнем характерного особенности и является произведением его на h-й корень из единицы.
7. . Пусть ω = 2π / h. Тогда матрица A аналогична матрице eA, следовательно, матрица спектра A инвариантен относительно умножения на e (соответствующий повороту комплексной плоскости на угол ω).
8. Если h>1, то существует матрица перестановок P такая, что

PAP – 1 = (0 A 1 0 0… 0 0 0 A 2 0… 0 ⋮ ⋮ ⋮ ⋮ 0 0 0 0… A h – 1 A h 0 0 0… 0), { displaystyle PAP ^ {- 1} = { begin {pmatrix} 0 A_ {1} 0 0 ldots 0 \ 0 0 A_ {2} 0 ldots 0 \ vdots vdots vdots vdots vdots \ 0 0 0 0 ldots A_ {h-1} \ A_ { h} 0 0 0 ldots 0 end {pmatrix}},}

где блоки вдоль главной диагонали представляют собой нулевые квадратные матрицы.

9. Формула Коллатца –Виландта : для всех неотрицательных ненулевых векторов x пусть f (x) будет минимальным значением [Ax] i / x i взято по всем таким образом, что x i ≠ 0. Тогда f вещественной функцией, максимум является единиц величиной Перрона – Фробениуса.

10. Собственное значение Перрона – Фробениуса удовлетворяет неравенствам

min i ∑ j a i j ≤ r ≤ max i ∑ j a i j. { displaystyle min _ {i} sum _ {j} a_ {ij} leq r leq max _ {i} sum _ {j} a_ {ij}.}

Пример A Знак равно (0 0 1 0 0 1 1 1 0) { displaystyle A = left ({ begin {smallmatrix} 0 0 1 \ 0 0 1 \ 1 1 0 end {smallmatrix} } right)}показывает, что (квадратные) нулевые матрицы по диагонали могут иметь разные размеры, блоки A j не обязательно должны быть квадратными, и h не обязательно делить n.

Дополнительные свойства

Пусть A – неприводимая неотрицательная матрица, тогда:

1. (I + A) – положительная матрица. (Мейер п. 8.3.5 с. 672 ).
2. Теорема Виландта. Если | B |
3. Если некоторая степень A приводима, то она полностью приводима, т.е. для некоторой матрицы перестановок P она верно, что: PA q P – 1 = (A 1 0 0… 0 0 A 2 0… 0 ⋮ ⋮ ⋮ ⋮ 0 0 0… A d) { displaystyle PA ^ {q} P ^ {- 1 } = { begin {pmatrix} A_ {1} 0 0 dots 0 \ 0 A_ {2} 0 dots 0 \ vdots vdots vdots vdots 0 0 0 dots A_ {d} \ end {pmatrix}}}, где A i – неприводимые матрицы, имеющие одинаковое максимальное собственное значение. эти матриц d является наибольшим общим делителем q и h, где h равно период A.
4. Если c (x) = x + c k1x + c k2x +… + c ksx является характерным многочленом A, в котором только не -перечисляются нулевые члены, тогда период A равен наибольшему общему делителю k 1, k 2,…, k s.
5. Cesàro средние значения : lim k → ∞ 1 / k ∑ i = 0,…, k A i / ri = (vw T), { displaystyle lim _ {k rightarrow infty} 1 / k sum _ {я = 0,…, k} A ^ {i} / r ^ {i} = (vw ^ {T}),}где левый и правый построенный для A нормированы так, что wv = 1. Кроме того, матрица vw является спектральной проекцией, проекцией на r, проекцию Перрона.
6. Пусть r – собственное значение Перрона – Фробениуса, тогда сопряженная матрица для (rA) положительна.
7. Если A имеет хотя бы один ненулевой диагональный элемент, то A примитивна.
8. Если 0 ≤ A < B, then rA≤ r B. Более того, если B неприводима, то неравенство строгое: r A< rB.

Матрица A является примитивен при условии, что он неотрицателен и A положителен для некоторого m, и, следовательно, A положительно для всех k ≥ m. Чтобы проверить примитивность, нужно определить, насколько большим может быть минимальное такое m, в зависимости от размера A:

• Если A – неотрицательная примитивная матрица размера n, то A положительна. Более того, это наилучший возможный результат, поскольку для матрицы M ниже степень M не является положительной для любого k < n − 2n + 2, since (M)11 = 0.

M = (0 1 0 0 ⋯ 0 0 0 1 0 ⋯ 0 0 0 0 1 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 0 0 ⋯ 1 1 1 0 0 ⋯ 0) { displaystyle M = left ({ begin {smallmatrix} 0 1 0 0 cdots 0 \ 0 0 1 0 cdots 0 \ 0 0 0 1 cdots 0 \ vdots vdots vdots vdots vdots \ 0 0 0 0 cdots 1 \ 1 1 0 0 cdots 0 end {smallmatrix}} right)}

Приложения

На тему неотрицательных матриц было написано множество книг, и теория Перрона – Фробениуса неизменно является центральной особенностью. Следующие ниже примеры, приведенные ниже, лишь поверхностно касаются ее обширной области применения.

Неотрицательные матрицы

Теорема Перрона – Фробениуса не применяется непосредственно к неотрицательным матрицам. Тем не менее, любая приводимая квадратная матрица A может быть записана в виде верхнетреугольного блока (известная как нормальная форма приводимой матрицы )

PAP = (B 1 ∗ ∗ ⋯ ∗ 0 B 2 ∗ ⋯ ∗ ⋮ ⋮ ⋮ ⋮ 0 0 0 ⋯ ∗ 0 0 0 ⋯ B h) { displaystyle left ({ begin {smallmatrix} B_ {1} * * cdots * \ 0 B_ {2} * cdots * \ vdots vdots vdots vdots \ 0 0 0 cdots * \ 0 0 0 cdots B_ {h} end {smallmatrix}} right)}

где P – это матрица перестановок, и каждый B i является квадратной матрицей, которая либо неприводима, либо равна нулю. Теперь, если A неотрицательна, то также и каждый блок PAP, более того, спектр A является просто объединением спектры B i.

Обратимость A также может быть изучена. Инверсия PAP (если она существует) должна иметь диагональные блоки формы B i, поэтому, если любой B i не является обратимым, то ни PAP, ни A. И наоборот, пусть D будет блочно-диагональной матрицей, соответств ующей PAP, другими словами PAP со звездочками, обнуленными. Если каждый B i обратим, то D тоже. а также D (PAP) равно единице плюс нильпотентная матрица. Но такая матрица всегда обратима (если N = 0, обратное к 1 – N равно 1 + N + N +… + N), поэтому PAP и A обратимы.

Следовательно, многие из спектральных свойств A можно вывести, применяя теорему к неприводимому B i. Например, корень Перрона – это максимум ρ (B i). Хотя все еще будут собственные векторы с неотрицательными компонентами, вполне возможно, что ни один из них не будет положительным.

Стохастические матрицы

Строка (столбец) стохастическая матрица – это квадратная матрица, каждая из строк (столбцов) которой состоит из неотрицательных действительных чисел, сумма которых равна единице. Теорема не может быть применена непосредственно к таким матрицам, потому что они не обязательно должны быть неприводимыми.

Если A является стохастическим по строкам, то вектор-столбец с каждой записью 1 является собственным вектором, соответствующим собственному значению 1, которое также является ρ (A) согласно замечанию выше. Это может быть не единственное собственное значение на единичной окружности: и соответствующее собственное подпространство может быть многомерным. Если A является стохастическим по строкам и неприводимым, то проекция Перрона также является стохастической по строкам и все ее строки равны.

Алгебраическая теория графов

Эта теорема находит особое применение в алгебраической теории графов. «Базовый граф» неотрицательной n-квадратной матрицы – это граф с вершинами, пронумерованными 1,…, n и дугой ij тогда и только тогда, когда A ij ≠ 0. Если базовый граф такой матрицы матрица сильно связна, то матрица неприводима, и поэтому теорема применима. В частности, матрица смежности сильно связного графа неприводима.

Конечные цепи Маркова

Теорема имеет естественную интерпретацию в теории конечных цепей Маркова (где это теоретико-матричный эквивалент сходимости неприводимой конечной цепи Маркова к ее стационарному распределению, сформулированный в терминах матрицы переходов цепи; см., например, статья о субсдвиге конечного типа ).

Компактные операторы

В более общем смысле его можно распространить на случай неотрицательных компактных операторов, которые во многом напоминают конечномерные матрицы. Их обычно изучают в физике под названием операторов переноса, а иногда и операторов Рюэля – Перрона – Фробениуса (после Дэвида Руэля ). В этом случае главное собственное значение соответствует термодинамическому равновесию динамической системы, а меньшие собственные значения – режимам распада системы, которая не находится в равновесии. Таким образом, теория предлагает способ обнаружить стрелу времени в том, что в противном случае могло бы показаться обратимым, детерминированным динамическим процессом, если рассматривать его с точки зрения топологии множества точек.

Методы доказательства

Общей чертой многих доказательств является теорема Брауэра о неподвижной точке. Другой популярный метод – это Wielandt (1950). Он использовал описанную выше формулу Коллатца -Виландта, чтобы расширить и прояснить работу Фробениуса. Другое доказательство основано на спектральной теории, часть аргументов которой заимствована.

Корень Перрона является строго максимальным собственным значением для положительных (и примитивных) матриц

Если A является положительной (или, в более общем смысле, примитивной) матрицей, то существует действительное положительное собственное значение r (Перрон – Фробениус собственное значение или корень Перрона), который строго больше по модулю, чем все другие собственные значения, следовательно, r – это спектральный радиус числа A.

Это утверждение не выполняется для общих неотрицательных неприводимых матриц, которые имеют h собственных значений с тем же абсолютным собственным значением, что и r, где h – период A.

Доказательство для положительных матриц

Пусть A – положительная матрица, предположим, что ее спектральный радиус ρ (A) = 1 (иначе рассмотрим A / ρ (A)). Следовательно, существует собственное значение λ на единичной окружности, а все остальные собственные значения меньше или равны 1 по модулю. Предположим, что на единичную окружность также попадает другое собственное значение λ ≠ 1. Тогда существует натуральное число m такое, что A – положительная матрица, а действительная часть λ отрицательна. Пусть ε – половина наименьшего диагонального элемента матрицы A, и положим T = A – εI, которая является еще одной положительной матрицей. Более того, если Ax = λx, то Ax = λx, таким образом, λ – ε является собственным значением T. Из-за выбора m эта точка лежит вне единичного круга, следовательно, ρ (T)>1. С другой стороны, все элементы в T положительны и меньше или равны элементам в A, поэтому по формуле Гельфанда ρ (T) ≤ ρ (A) ≤ ρ (A) = 1. Это противоречие означает, что λ = 1 и других собственных значений на единичной окружности быть не может.

Абсолютно те же аргументы могут быть применены к случаю примитивных матриц; нам просто нужно упомянуть следующую простую лемму, разъясняющую свойства примитивных матриц.

Лемма

Для неотрицательного A, предположим, что существует m такое, что A положительно, тогда все A, A, A,… положительны.

A = AA, поэтому он может иметь нулевой элемент только в том случае, если некоторая строка A полностью равна нулю, но в этом случае та же строка A будет нулем.

Применяя те же аргументы, что и выше для примитивных матриц, докажите основное утверждение.

Степенной метод и положительная собственная пара

Для положительной (или, в более общем смысле, неприводимой неотрицательной) матрицы A доминирующий собственный вектор является действительным и строго положительным (для не- отрицательный A, соответственно неотрицательный.)

Это может быть установлено с помощью метода степени, который утверждает, что для достаточно общей (в смысле ниже) матрицы A последовательность векторов b k + 1 = Ab k / | Ab k | сходится к собственному вектору с максимальным собственным значением. (Начальный вектор b 0 может быть выбран произвольно, за исключением некоторой установки нуля меры). Начиная с неотрицательного вектора b 0, получается последовательность неотрицательных векторов b k. Следовательно, предельный вектор также неотрицателен. По степенному методу этот предельный вектор является доминирующим собственным вектором для A, что доказывает утверждение. Соответствующее собственное значение неотрицательно.

Для доказательства требуются два дополнительных аргумента. Во-первых, степенной метод сходится для матриц, у которых нет нескольких собственных значений, имеющих то же абсолютное значение, что и максимальное. Аргумент предыдущего раздела гарантирует это.

Во-вторых, чтобы гарантировать строгую положительность всех компонент собственного вектора для случая неприводимых матриц. Это следует из следующего факта, представляющего самостоятельный интерес:

Лемма: учитывая положительную (или, в более общем смысле, неприводимую неотрицательную) матрицу A и v как любой неотрицательный собственный вектор для A, тогда она обязательно строго положительна и соответствующее собственное значение также строго положительно.

Доказательство. Одно из определений неприводимости неотрицательных матриц состоит в том, что для всех индексов i, j существует m такое, что (A) ij строго положительно. Для неотрицательного собственного вектора v и того, что по крайней мере один из его компонентов утверждает, что j-й строго положителен, соответствующее собственное значение строго положительно, действительно, если n такое, что (A) ii>0, отсюда: rv i = Av i ≥ (A) iivi>0. Следовательно, r строго положительно. Собственный вектор – строгая положительность. Тогда для m, такого что (A) ij>0, следовательно: rv j = (Av) j ≥ (A) ijvi>0, следовательно, v j строго положительно, т. е. собственный вектор строго положителен.

Кратность один

Этот раздел доказывает, что собственное значение Перрона – Фробениуса является простым корнем характеристического полинома матрицы. Следовательно, собственное подпространство, связанное с собственным значением Перрона – Фробениуса r, одномерно. Аргументы здесь близки к аргументам Мейера.

Дан строго положительный собственный вектор v, соответствующий r, и другой собственный вектор w с тем же собственным значением. (Векторы v и w могут быть выбраны действительными, поскольку оба A и r действительны, поэтому нулевое пространство Ar имеет базис, состоящий из действительных векторов.) Предполагая, что хотя бы один из компонентов w положителен (в противном случае умножьте w на −1). Если задано максимально возможное α такое, что u = v- α w неотрицательно, то одна из компонент u равна нулю, иначе α не является максимальным. Вектор u – это собственный вектор. Оно неотрицательно, поэтому по лемме, описанной в предыдущем разделе, неотрицательность подразумевает строгую положительность для любого собственного вектора. С другой стороны, как указано выше, по крайней мере, одна компонента u равна нулю. Противоречие означает, что w не существует.

Случай: нет жордановых ячеек, соответствующих собственному значению Перрона – Фробениуса r и всем другим собственным значениям, имеющим такое же абсолютное значение.

Если есть жорданова клетка, то бесконечная норма (A / r) ∞ стремится к бесконечности при k → ∞, но это противоречит существованию положительный собственный вектор.

Дано r = 1 или A / r. Пусть v – строго положительный собственный вектор Перрона – Фробениуса, поэтому Av = v, тогда:

‖ v ‖ ∞ = ‖ A kv ‖ ∞ ≥ ‖ A k ‖ ∞ min i (vi), ⇒ ‖ A k ‖ ∞ ≤ ‖ V ‖ / мин я (vi) { displaystyle | v | _ { infty} = | A ^ {k} v | _ { infty} geq | A ^ {k} | _ { infty} min _ {i} (v_ {i}), ~~ Rightarrow ~~ | A ^ {k} | _ { infty} leq | v | / min _ {i } (v_ {i})}Итак, A ∞ ограничено для всех k. Это дает еще одно доказательство того, что не существует собственных значений, имеющих большее абсолютное значение, чем значение Перрона – Фробениуса. Это также противоречит существованию жордановой клетки для любого собственного значения, которое имеет абсолютное значение, равное 1 (в частности, для Перрона – Фробениуса), поскольку существование жордановой клетки означает, что A ∞ неограниченно. Для матрицы два на два:

J k = (λ 1 0 λ) k = (λ kk λ k – 1 0 λ k), { displaystyle J ^ {k} = { begin {pmatrix} lambda 1 \ 0 lambda end {pmatrix}} ^ {k} = { begin {pmatrix} lambda ^ {k} k lambda ^ {k-1} \ 0 lambda ^ {k} end { pmatrix}},}

, следовательно, J ∞ = | k + λ | (для | λ | = 1), поэтому при k стремится к бесконечности. Поскольку J = C AC, то A ≥ J / (C C), поэтому оно также стремится к бесконечности. Полученное противоречие означает, что для соответствующих собственных значений нет жордановых клеток.

Объединение двух приведенных выше утверждений показывает, что собственное значение Перрона – Фробениуса r является простым корнем характеристического многочлена. В случае непримитивных матриц существуют другие собственные значения, которые имеют то же абсолютное значение, что и r. То же самое верно и для них, но требует дополнительной работы.

Никаких других неотрицательных собственных векторов

Для положительной (или, в более общем смысле, неприводимой неотрицательной матрицы) A, собственный вектор Перрона – Фробениуса является единственным (с точностью до умножения на константу) неотрицательным eigenvector for A.

Other eigenvectors must contain negative or complex components since eigenvectors for different eigenvalues are orthogonal in some sense, but two positive eigenvectors cannot be orthogonal, so they must correspond to the same eigenvalue, but the eigenspace for the Perron–Frobenius is one-dimensional.

Assuming there exists an eigenpair (λ, y) for A, such that vector y is positive, and given (r, x), where x – is the left Perron–Frobenius eigenvector for A (i.e. eigenvector for A), then rxy = (x A) y = x (Ay) = λxy, also x y>0, so one has: r = λ. Since the eigenspace for the Perron–Frobenius eigenvalue r is one-dimensional, non-negative eigenvector y is a multiple of the Perron–Frobenius one.

Collatz–Wielandt formula

Given a positive (or more generally irreducible non-negative matrix) A, one defines the function f on the set of all non-negative non-zero vectors x such th at f (x) – минимальное значение [Ax] i / x i, взятое для всех тех i, что x i ≠ 0. Тогда f равно действительная функция, максимум которой является собственным значением Перрона – Фробениуса r.

Для доказательства мы обозначим максимум f значением R. Доказательство требует показать R = r. Подставляя собственный вектор Перрона-Фробениуса v в f, получаем f (v) = r и заключаем, что r ≤ R. Для противоположного неравенства рассмотрим произвольный неотрицательный вектор x и положим ξ = f (x). Определение f дает 0 ≤ ξx ≤ Ax (покомпонентно). Теперь мы используем положительный правый собственный вектор w для A для собственного значения Перрона-Фробениуса r, тогда ξ w x = w ξx ≤ w (Ax) = (w A) x = r w x. Следовательно, f (x) = ξ ≤ r, что подразумевает R ≤ r.

проекция Перрона как предел: A / r

Пусть A будет положительной (или, в более общем смысле, примитивной) матрицей, и пусть r его собственное значение Перрона – Фробениуса.

1. Существует предел A / r для k → ∞, обозначим его через P.
2. P – оператор проекции : P = P, который коммутирует с A: AP = PA.
3. Изображение P одномерно и натянуто на собственный вектор Перрона – Фробениуса v (соответственно для P – на собственный вектор Перрона – Фробениуса w для A).
4. P = vw, где v, w нормированы так, что wv = 1.
5. Следовательно, P – положительный оператор.

Следовательно, P является a для собственного значения Перрона – Фробениуса r и называется проекцией Перрона. Сказанное выше утверждение неверно для общих неотрицательных неприводимых матриц.

Фактически приведенная выше формула (кроме формулы 5) действительна для любой матрицы M, такой что существует собственное значение r, которое строго больше других собственных значений по модулю и является простым корнем характеристики многочлен. (Эти требования выполняются для примитивных матриц, как указано выше).

Учитывая, что M диагонализуема, M сопряжена с диагональной матрицей с собственными значениями r 1,…, r n на диагонали (обозначим r 1 = г). Матрица M / r будет сопряженной (1, (r 2 / r),…, (r n / r)), которая стремится к (1,0, 0,…, 0) при k → ∞, поэтому предел существует. Тот же метод работает для общего M (без предположения, что M диагонализуема).

Свойства проекции и коммутативности являются элементарными следствиями определения: MM / r = M / r M; P = lim M / r = P. Третий факт также элементарен: M (Pu) = M lim M / ru = lim rM / ru, поэтому переход к пределу дает M (Pu) = r (Pu), так что образ P лежит в собственном r-подпространстве для M, которое по предположениям одномерно.

Обозначение v, r-собственный вектор для M (w для M). Столбцы P кратны v, потому что ими покрывается образ P. Соответственно, строки w. Итак, P принимает форму (a v w) для некоторого a. Следовательно, его след равен (a w v). След проектора равен размеру его изображения. Ранее было доказано, что он не более чем одномерный. Из определения видно, что P одинаково действует на r-собственный вектор для M. Значит, он одномерный. Таким образом, выбор (wv) = 1 влечет P = vw.

Неравенства для собственного значения Перрона – Фробениуса

Для любой неотрицательной матрицы A ее собственное значение Перрона – Фробениуса r удовлетворяет неравенству:

r ≤ max i ∑ j A i j. { displaystyle r ; leq ; max _ {i} sum _ {j} A_ {ij}.}

Это не относится к неотрицательным матрицам: для любой матрицы A с собственным значением λ { displaystyle scriptstyle lambda}это правда, что | λ | ≤ max i ∑ j | A i j | { displaystyle scriptstyle | lambda | ; leq ; max _ {i} sum _ {j} | A_ {ij} |}. Это непосредственное следствие теоремы Гершгорина о круге. Однако другое доказательство более прямое:

Любая матрица , индуцированная норма удовлетворяет неравенству ‖ A ‖ ≥ | λ | { Displaystyle scriptstyle | А | geq | lambda |}для любого собственного значения λ { displaystyle scriptstyle lambda}потому что, если x { displaystyle scriptstyle x}– соответствующий собственный вектор, ‖ A ‖ ≥ | A x | / | х | = | λ x | / | х | = | λ | { Displaystyle scriptstyle | А | geq | Топор | / | х | = | лямбда х | / | х | = | lambda |}. Бесконечная норма матрицы – это максимум суммы строк: ‖ A ‖ ∞ = max 1 ≤ i ≤ m ∑ j = 1 n | A i j |. { Displaystyle scriptstyle left | A right | _ { infty} = max limits _ {1 leq i leq m} sum _ {j = 1} ^ {n} | A_ {ij} |.}Следовательно, необходимое неравенство в точности равно ‖ A ‖ ∞ ≥ | λ | { Displaystyle scriptstyle | А | _ { infty} geq | lambda |}, примененный к неотрицательной матрице A.

Другое неравенство:

min i ∑ j A ij ≤ r. { Displaystyle мин _ {я} сумма _ {j} A_ {ij} ; leq ; r.}

Этот факт характерен для неотрицательных матриц; для общих матриц ничего подобного нет. Учитывая, что A положительно (а не только неотрицательно), тогда существует положительный собственный вектор w такой, что Aw = rw и наименьшая компонента w (скажем, w i) равна 1. Тогда r = (Aw) i ≥ чисел сумма в строке i матрицы A. Таким образом, минимальная сумма строки дает нижнюю границу для r, и это наблюдение можно распространить на все неотрицательные матрицы по непрерывности.

Другой способ аргументировать это – использовать формулу Коллатца -Виландта. Берется вектор x = (1, 1,…, 1) и сразу получается неравенство.

Дальнейшие доказательства

Проекция Перрона

Теперь доказательство проводится с использованием спектрального разложения. Уловка здесь состоит в том, чтобы отделить корень Перрона от других значений. Спектральная проекция, связанная с корнем Перрона, называется Перрона, и она проекционным следующим своим:

Проекция Перрона неприводимой неотрицательной квадратной матрицы является положительной матрицей.

Выводы Перрона, а также (1) – (5) теоремы являются следствиями этого результата. Ключевым моментом является то, что положительная проекция всегда имеет первый ранг. Это означает, что если A – неприводимая неотрицательная квадратная матрица, то алгебраическая и геометрическая кратности ее корня Перронаны единице. Также, если P – его проекция Перрона, то AP = PA = ρ (A) P, так что каждый столбец P является положительным правым собственным вектором A, каждая строка является положительным левым собственным вектором. Более того, если Ax = λx, то PAx = λPx = ρ (A) Px, что означает Px = 0, если λ ≠ ρ (A). Таким образом единственными положительными собственными руками являются те, которые связаны с ρ (A). Если A – примитивная матрица с ρ (A) = 1, то ее можно разложить как P ⊕ (1 – P) A, так что A = P + (1 – P) A. По мере увеличения n второй из членов этих убывает до нуля, оставляя P как предел для A при n → ∞.

Степенной метод – удобный способ вычислить проекцию Перрона примитивной матрицы. Если v и w – положительные элементы строк и столбцов, которые он генерирует, то проекция Перрона равна просто wv / vw. Спектральные проекции не заблокированы аккуратно, как в форме Джордана. Здесь наложены друг на друга, и каждый, как правило, сложные элементы, распространяющиеся на все четыре угла квадратной матрицы. Тем не менее, они сохраняют взаимную ортогональность, что облегчает разложение.

Периферийная проекция

Анализ, когда A является несократимым и неотрицательным, в целом. Проекция Перрона по-прежнему положительна, но теперь могут быть другие собственные значения модуля ρ (A), которые исключают использование методов степеней и предотвращают убывание степеней (1 – P) A, как в примитивном случае, когда ρ (A) = 1. Итак, мы рассматриваем периферийную проекцию, которая является спектральной проекцией A, которая является всем собственным значением, имеющим модуль ρ (A). Затем можно показать, что периферийная проекция неприводимой неотрицательной квадратной матрицы является неотрицательной матрицей с положительной диагональю.

Цикличность

Предположим также, что ρ (A) = 1 и A имеет h собственных значений на единичной окружности. Если P – периферийная проекция, тогда матрица R = AP = PA неотрицательна и неприводима, R = P, а циклическая группа P, R, R,…., R представляет гармоники матрицы A. Спектральная проекция матрицы A в собственном значении λ на единичной окружности задается формулой h – 1 ∑ 1 h λ – k R k { displaystyle scriptstyle h ^ {- 1} sum _ {1} ^ {h} lambda ^ {- k} R ^ {k }}. Все эти проекции (включая проекцию Перрона) имеют одинаковую положительную диагональ, более того, если выбрать любую из них, а взять модуль каждой записи, неизменно будет проекция Перрона. Некоторая работа осла все еще необходима, чтобы установить циклические свойства (6) – (8), но, по сути, это просто вопрос ручки поворота. Спектральное разложение A определяет выражением A = R ⊕ (1 – P) A, поэтому разница между A и R равна A – R = (1 – P) A, представляя переходные процессы A, которые в итоге затухают до нуля. P можно вычислить как предел A при n → ∞.

Контрпримеры

Матрицы L = (1 0 0 1 0 0 1 1 1) { displaystyle left ({ begin {smallmatrix} 1 0 0 \ 1 0 0 \ 1 1 1 end {smallmatrix}} right)}, P = (1 0 0 1 0 0 – 1 1 1) { displaystyle left ({ begin {smallmatrix} 1 0 0 \ 1 0 0 \! ! ! – 1 1 1 end {smallmatrix}} right)}, T = (0 1 1 1 0 1 1 1 0) { displaystyle left ({ begin {smallmatrix} 0 1 1 \ 1 0 1 \ 1 1 0 end { smallmatrix}} right)}, M = (0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0) { displaystyle left ({ begin {smallmatrix} 0 1 0 0 0 \ 1 0 0 0 0 0 \ 0 0 0 1 0 \ 0 0 0 0 1 \ 0 0 1 0 0 end {smallmatrix}} <справа)}306>приведите простые примеры того, что может пойти не так, если необходимые условия не будут выполнены. Легко, что и перронная, и периферийная проекции L равны P, таким образом, когда исходная матрица приводима, проекции потерять неотрицательность, и нет возможности выразить их как пределы ее возможностей. Матрица T является примером примитивной матрицы с нулевой диагональю. Если диагональ неприводимой неотрицательной квадратной матрицы не равна нулю, тогда матрица должна быть примитивной, но этот пример демонстрирует, что обратное неверно. M – пример матрицы с используемыми спектральными зубцами. Если ω = e, то ω = 1 и собственные значения M равны {1, ω, ω, ω}, поэтому ω и ω отсутствуют.

Терминология

Проблема, которая вызывает путаницу, заключается в отсутствии стандартизации в определениях. Например, некоторые используют термины строго положительный и положительный для обозначения>0 и ≥ 0 соответственно. В этой статье положительное означает>0, неотрицательное означает ≥ 0. Еще одна неприятная область касается разложимости и сводимости: неприводимый – это перегруженный термин. Во избежание такой ненулевую неотрицательную квадратную матрицу A, что 1 + A примитивно, иногда называют связной. Тогда неприводимые неотрицательные квадратные матрицы и связанные матрицы являются синонимами.

Неотрицательный собственный вектор часто регулируется, чтобы сумма его компонентов была равна единице; в этом случае собственный вектор является вектором распределения вероятностей и иногда называется стохастическим собственным вектором.

Собственное значение Перрона – Фробениуса и доминирующее собственное значение – альтернативные названия корня Перрона. Спектральные проекции также известны как спектральные проекторы и спектральные идемпотенты. Период иногда называют индексом импримитивности или порядком цикличности.

См. Также

Примечания

Ссылки

Исходные статьи

• Перрон, Оскар (1907), «Теория Цура Матрицы» «, Mathematische Annalen, 64(2): 248–263, doi : 10.1007 / BF01449896, hdl : 10338.dmlcz / 104432
• Фробениус, Георг (май 1912 г.), «Ueber Matrizen aus nicht negativen Elementen», Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften : 456–477,
• Георг (1908), «Über Matrizen aus positiven Elementen, 1», Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: 471–476
• Frobenius, Georg (1909), «Uber Matrizen aus Positiven Elementen, «berchen» Akademie der Wissenschaften: 514–518
• Гантмахер, Феликс (2000) [1959], Теория матриц, Том 2, A MS Chelsea Publishing, ISBN 978-0-8218-2664-5 (издание 1959 года имело другое название: «Приложения теории матриц». Также нумерация глав в двух изданиях разная.)
• Лэнгвилл, Эми; Мейер, Карл (2006), рейтинг страницы Google и выше, Princeton University Press, doi : 10.1007 / s10791-008-9063-y, ISBN 978-0-691-12202-1
• Кинер, Джеймс (1993), «Теорема Перрона – Фробениуса и рейтинг футбольных команд», SIAM Review, 35 (1): 80– 93, doi : 10.1137 / 1035004, JSTOR 2132526
• Мейер, Карл (2000), Матричный анализ и прикладная линейная алгебра (PDF), SIAM, ISBN 978-0-89871-454-8, заархивировано из оригинала (PDF) на 07.03.2010
• Романовский В. (1933), “Sur les zéros des matrices stocastiques”, Bulletin de la Société Mathématique de France, 61 : 213–219, doi : 10.24033 / bsmf.1206
• Коллатц, Лотар (1942), «Einschließungssatz für die charakteristischen Zahlen von Matrizen», Mathematische Zeitschrift, 48 (1): 221–226, doi : 10.1007 / BF01180013
• Виландт, Гельмут (1950), «Unzerlegbare, nicht negative Matrizen», Mathematische Zeitschrift, 52 (1): 642–648, doi : 10.1007 / BF02230720, hdl : 10338.dmlcz / 100322

Дополнительная литература

• Абрахам Берман, Роберт Дж. Племмонс, Неотрицательные матрицы в математических науках, 1994, SIAM. ISBN 0-89871-321-8.
• Крис Годсил и Гордон Ройл, Алгебраическая теория графов, Springer, 2001.
• А. Грэм, Неотрицательные матрицы и применимые темы в линейной алгебре, John Wiley Sons, Нью-Йорк, 1987.
• R. А. Хорн и К.Р. Джонсон, Матричный анализ, Cambridge University Press, 1990
• Бас Лемменс и Роджер Нуссбаум, Нелинейная теория Перрона-Фробениуса, Кембриджские трактаты по математике 189, Кембриджский университет. Press, 2012.
• С. П. Мейн и Р.Л. Твиди, Цепи Маркова и стохастическая стабильность Лондон: Springer-Verlag, 1993. ISBN 0-387-19832-6 (2-е издание, Cambridge University Press, 2009)
• Хенрик Минк, неотрицательные матрицы, John Wiley Sons, Нью-Йорк, 1988, ISBN 0-471-83966-3
• Сенета, Э. Неотрицательные матрицы и цепи Маркова. 2-е изд. изд., 1981, XVI, 288 стр., Серия Springer в мягкой обложке по статистике. (Первоначально опубликовано Allen Unwin Ltd., Лондон, 1973 г.) ISBN 978-0-387-29765-1
• Супруненко, Д.А. (2001) [1994], Энциклопедия математики, EMS Press (Утверждение, что A j имеет порядок н / ч в конце утверждения Теорема неверна.)
• Варга, Ричард С. (2002), Матричный итерационный анализ (2-е изд.), Springer-Verlag.