next up previous
Next: Equilibrium eigenvector Up: Probabilistic de Bruijn Previous: Largest eigenvalue

Second eigenvalue and convergence

For strictly positive matrices the maximum eigenvalue is unique and bounded away from the remaining eigenvalues. Nevertheless the size of the second largest eigenvalue is influential in determining such matters as the rate of convergence of the technique of successive squaring, and in any event governs the rate of approach to the equilibrium eigenvector when the matrix is applied iteratively to a trial vector.

There are two familiar formulations for bounds on the modulus of the second eigenvalue (which neither has to be real nor unique). One is essentially equivalent to using the spectral theorem to subtract out the projection operator belonging to the largest eigenvalue in order to apply the Gerschgorin limits anew [20, p. 51,]. The second interprets the matrix as an operator on a projective space, for which the largest eigenvector becomes a fixed point and the remaining eigenvalues refer to movement within the projective space.

The second approach is quite reasonable considering that eigenvectors in linear spaces correspond to fixed points in projective spaces. The stability of the fixed point is determined to a certain extent by the Jacobian --- corresponding to the derivative --- of the mapping at the fixed point, but in more detail by considering the remaining eigenvalues individually. In other words, the Jacobian matrix rather than just the Jacobian determinant should be consulted.

Birkhoff [22] has emphasized the projective point of view, but the most accessible account is probably the painstaking derivation from first principles by Bauer [23].

In any event, suppose that A is a strictly positive matrix for which

and that is the Frobenius-Perron, or dominant, eigenvalue of A. Then any other eigenvalue must satisfy

Hopf [24] obtained an alternative version,

The bounds for both estimates are actually attained for certain matrices, making them optimal in the absence of further information concerning A. When the eigenvector corresponding to is known, some further improvement is possible [25].

These results would not apply directly to a de Bruijn matrix because of its sparsity. Yet it has a power filled solidly with 1's whose oscillation vanishes, forcing the second largest eigenvalue of the power to be identically zero, in agreement with the characteristic equation. Less extreme conclusions govern probabilistic de Bruijn matrices, but uniformity would still surely speed any approach to equilibrium.



next up previous
Next: Equilibrium eigenvector Up: Probabilistic de Bruijn Previous: Largest eigenvalue



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx