Smoothing algorithm for the maximal eigenvalue of non-defective positive matrices

1.   Introduction

A matrix $A$ with all elements greater than zero is referred to as a positive matrix and is denoted by $A > 0$. Positive matrices possess several significant properties. Perron ^[1] first proposed that if $A$ is a positive matrix, then the spectral radius is an eigenvalue of $A$. This eigenvalue, denoted by $\rho (A)$, is called the maximal eigenvalue of $A$ or the Perron root of $A$, and $\rho (A)$ dominates all other eigenvalues in modulus.

If $A = ({{a}_{ij}})$, then $A$ is called nonnegative if ${{a}_{ij}}\ge \text{0}$ and is denoted by $A\ge 0$. Nonnegative matrices are frequently encountered in real-life applications. Frobenius ^[1] extended Perron's theory to nonnegative matrices and nonnegative irreducible matrices, leading to the rapid development of the nonnegative matrix theory. The famous Perron-Frobenius theorem is widely used in both theory and practice. Estimating the range of maximal eigenvalue of positive matrices is a popular topic in the nonnegative matrix theory and has been extensively and thoroughly studied in ^{[2,3,4,5,6,7,8,9,10]}.

For any positive integer $n$, let $\langle n \rangle \text{ = }\left\{ \text{1, 2, }\cdots, n \right\}$. Given $A = {{({{a}_{ij}})}_{n\times n}}\ge 0$, we define

Frobenius ^[1] obtained the following classical conclusion:

Additionally, equality in (1) is achieved when the sum of each row of the matrix $A$ is equal. A similar result holds for the column with the transpose matrix ${{A}^{\text{T}}}$ in place of $A$. The above inequality implies that the maximal eigenvalue $\rho (A)$ of a nonnegative square matrix $A$ is between the smallest row sum $r(A)$ and the largest row sum $R(A)$. This observation provides a convenient and efficient method for estimating the maximal eigenvalue using the elements of $A$.

The class of positive matrices, which is the subclass of nonnegative matrices, shares similar properties with nonnegative matrices. The generalization of the result in (1) was presented in ^[2,3,4] to improve the bounds of the maximal eigenvalues of positive matrices.

Minc ^[5] made improvements to the bounds in (1) for nonnegative matrices with nonzero row sums, resulting in the following:

Liu ^[6] generalized the above result further and obtained the following conclusion:

where $k$ is any nonnegative integer and $m$ is any positive integer. The same is true for column sums.

Based on Eq (2), Liu et al. ^[7] gave an innovative result as follows:

where $B = {{\left(A+I \right)}^{n-1}}$ and $I$ is the identity matrix of order $n$. The same is true for column sums.

If we set $m\text{ = 1}$ in (2), we will obtain

The boundaries are further generalized in ^[8] as follows:

where $B$ is an arbitrary matrix that has positive row sums.

The following is the concept of a non-defective matrix. In linear algebra, a square matrix that lacks a full basis of eigenvectors and cannot be diagonalized is referred to as a defective matrix. Specifically, a matrix of order $n$ is considered non-defective if it contains $n$ linearly independent eigenvectors.

This paper is dedicated to the estimation and calculation of the maximal eigenvalue of a positive matrix. Initially, we present monotonically increasing lower-bound estimations and monotonically decreasing upper-bound estimations for the maximal eigenvalue of a positive matrix. Additionally, we rigorously prove the monotonicity and convergence of these estimations. Notably, if the positive matrix is non-defective, we provide a smoothing algorithm to calculate the maximal eigenvalue of such a non-defective positive matrix.

2.   Main results

To derive our conclusions, we will recall some essential lemmas as follows.

Lemma 1. ^[5] Let $\lambda$ be an eigenvalue of the square matrix $A$ of order $n$ and let $U = {{({{u}_{1}}, {{u}_{2}}, \cdots, {{u}_{n}})}^{\text{T}}}$ and $V = {{({{v}_{1}}, {{v}_{2}}, \cdots, {{v}_{n}})}^{\text{T}}}$ be eigenvectors corresponding to $\lambda$ of ${{A}^{\text{T}}}$ and $A$, respectively, then

Lemma 2. ^[5] If ${{q}_{t}} > 0, t\in \langle n \rangle$, then for any real numbers ${{p}_{t}}, t\in \langle n \rangle$, the following inequality holds:

Now, we present the upper and lower bounds on the maximal eigenvalue of a positive matrix.

Theorem 1. Given a positive matrix $A = {{\left({{a}_{ij}} \right)}_{n\times n}}$, let ${{B}_{1}} = {{\left(A+\alpha I \right)}^{n-1}}, {{B}_{2}} = {{\left(A-\beta I \right)}^{n-1}}$, where $\alpha = \underset{i}{\mathop{\max\limits}}\, \left\{ {{a}_{ii}} \right\}, \beta = \underset{i}{\mathop{\min\limits}}\, \left\{ {{a}_{ii}} \right\}$. If ${{r}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right)\ne 0$, ${{c}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right)\ne 0$, $i\in \langle n \rangle$, then for any positive integer $k$, we have

Proof. First, we prove ${{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right) > 0$ with the condition ${{r}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right)\ne 0$. For any positive integer $k\ge 2$, the element of the matrix ${{A}^{k-1}}{{B}_{1}}{{B}_{2}}$ located in the $t$-th row and the $j$-th column is denoted by ${{\left({{A}^{k-1}}{{B}_{1}}{{B}_{2}} \right)}_{tj}}$. Note that ${{A}^{k}}{{B}_{1}}{{B}_{2}} = A{{A}^{k-1}}{{B}_{1}}{{B}_{2}}$. We have

It is evident that ${{B}_{1}} = {{\left(A+\alpha I \right)}^{n-1}}$ and ${{B}_{2}} = {{\left(A-\beta I \right)}^{n-1}}$ are nonnegative. Therefore, $A{{B}_{1}}{{B}_{2}}$ is nonnegative and ${{r}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right) > 0$ holds under the restriction that ${{r}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right)\ne 0$. As $A$ is a positive matrix, that is, ${{a}_{ij}} > 0$, $i, j\in \langle n \rangle$, we immediately obtain ${{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right) > 0$ from Eq (8). By employing the same approach, we also obtain ${{c}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right) > 0$ if ${{c}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right)\ne 0$, $i\in \langle n \rangle$. These assertions ensure that the expressions in Eqs (6) and (7) are valid.

Now, we assume $X = {{({{x}_{1}}, {{x}_{2}}, \cdots, {{x}_{n}})}^{\text{T}}} > 0$ is the eigenvector of the matrix ${{A}^{\text{T}}}$ corresponding to $\rho (A)$, that is, ${{A}^{\text{T}}}X = \rho (A)X$. Clearly, the maximal eigenvalues of the matrix polynomials

and

are ${{\rho }^{k+2}}\left(A \right){{\left[\rho \left(A \right)+\alpha \right]}^{n-1}}{{\left[\rho \left(A \right)-\beta \right]}^{n-1}}$ and ${{\rho }^{k}}\left(A \right){{\left[\rho \left(A \right)+\alpha \right]}^{n-1}}{{\left[\rho \left(A \right)-\beta \right]}^{n-1}}$, respectively. Therefore, we obtain

and

Based on Lemma 1, we have

and

Moreover, we must have

This is guaranteed by the previous proof ${{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right) > 0$ and

Therefore, according to Eqs (9) and (10), we can get

It follows from Lemma 2 that

that is,

Therefore, inequality (6) is proved. Similarly, inequality (7) holds.

Remark 1. From the formula

in (8), we can observe that ${{r}_{i}}\left({{A}^{k+2}}{{B}_{1}}{{B}_{2}} \right), {{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right)$ can be calculated by induction. In addition, a new matrix multiplication technique known as the semitensor product of matrices (STP) has been developed in recent years, which offers more powerful functionality compared to traditional matrix multiplication ^[11,12,13]. This implies that it is not difficult to compute the upper and lower bounds of $\rho (A)$.

In the following, we prove the convergence of the upper and lower bound expressions in Theorem 1 when the positive integer $k\to \infty$.

Theorem 2. Under the assumptions of Theorem 1, the following limits

exist, and $\rho (A)$ satisfies the following inequalities:

Proof. For any positive integer $k\ge 2$, according to (8) and Lemma 2, we have

The above inequality shows that

Therefore, we acquire

That is to say, the following sequence

is monotonically decreasing with respect to $k$. On the other hand, by Theorem 1 we know that the sequence has a lower bound $\rho \left(A \right)$. Based on the monotonicity bounded criterion, we conclude that

exists and is not less than $\rho \left(A \right)$. Similarly, the sequence

increases monotonically with respect to $k$ and has an upper bound $\rho \left(A \right)$ according to (6) in Theorem 1. Therefore, we derive that

exists and is not more than $\rho \left(A \right)$. Using the same approach, we can establish analogous results for column rows when ${{c}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right)\ne 0$, $i\in \langle n \rangle$.

Theorem 2 discusses the upper and lower bounds on the maximum eigenvalue of a positive matrix and proves that the sequence $\left\{ \underset{i}{\mathop{\max\limits}}\, \sqrt{\dfrac{{{r}_{i}}\left({{A}^{k+2}}{{B}_{1}}{{B}_{2}} \right)}{{{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right)}} \right\}$ decreases monotonically and has a lower bound $\rho \left(A \right)$, while the sequence $\left\{ \underset{i}{\mathop{\min\limits}}\, \sqrt{\dfrac{{{r}_{i}}\left({{A}^{k+2}}{{B}_{1}}{{B}_{2}} \right)}{{{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right)}} \right\}$ increases monotonically and has an upper bound $\rho \left(A \right)$. It is natural to wonder whether $\underset{k\to \infty }{\mathop{\lim\limits}}\, \underset{i}{\mathop{\max\limits}}\, \sqrt{\dfrac{{{r}_{i}}\left({{A}^{k+2}}{{B}_{1}}{{B}_{2}} \right)}{{{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right)}}$ or $\underset{k\to \infty }{\mathop{\lim\limits}}\, \underset{i}{\mathop{\min\limits}}\, \sqrt{\dfrac{{{r}_{i}}\left({{A}^{k+2}}{{B}_{1}}{{B}_{2}} \right)}{{{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right)}}$ is then equal to $\rho \left(A \right)$? In general, it is difficult to prove

Indeed, in special cases we have some elegant conclusions. The following are the results for a non-defective positive matrix.

Theorem 3. Under the assumptions of Theorem 1, if the positive matrix $A = {{\left({{a}_{ij}} \right)}_{n\times n}}$ is non-defective, then we have

Proof. Without loss of generality, it may be assumed that ${{\lambda }_{1}}, {{\lambda }_{2}}, \cdots, {{\lambda }_{n-1}}, \rho \left(A \right)$ are the eigenvalues of the matrix $A$ such that

The corresponding eigenvector family is ${{X}_{1}}, {{X}_{2}}, \cdots, {{X}_{n\text{-1}}}, {{X}_{n}}$, in which

Since $A$ is non-defective, the eigenvector family ${{X}_{1}}, {{X}_{2}}, \cdots, {{X}_{n\text{-1}}}, {{X}_{n}}$ forms a basis of the $n$-dimensional vector space. Moreover, we have

where ${{\left({{A}^{k+1}} \right)}_{it}}$ denotes the element of the matrix ${{A}^{k+1}}$ located in the $i$-th row and the $t$-th column and ${{\left(A{{B}_{1}}{{B}_{2}} \right)}_{tj}}$ denotes the element of the matrix $A{{B}_{1}}{{B}_{2}}$ located in the $t$-th row and the $j$-th column, respectively. Similarly, we have

Now, we define a special vector as follows:

It is obvious that $Y$ is a positive vector since ${{r}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right)\ne 0$ (more precisely, ${{r}_{i}}\left(A{{B}_{1}}{{B}_{2}} \right) > 0$), $i\in \langle n \rangle$.

Thus, $Y$ can be expressed as

where ${{C}_{1}}, {{C}_{2}}, \cdots, {{C}_{n-1}}, {{C}_{n}}$ are not all zero. Together with Eqs (13) and (14), one can get

On the other hand, we have

and

in which ${{\left({{A}^{k+1}}Y \right)}_{i}}$ and ${{\left({{A}^{k-1}}Y \right)}_{i}}$ denote the $i$-th coordinates of the vectors ${{A}^{k+1}}Y$ and ${{A}^{k-1}}Y$, respectively. Combined with Eqs (15)–(17), we obtain

Take the limit on both sides of Eq (18), and we acquire

Therefore, the equality in (11) holds. Similarly, we can prove that the corresponding result holds for the column.

Remark 2. Equations (11) and (12) in Theorem 3 show that for a non-defective positive matrix $A$, the limits of the maximum and minimum values of

are equal to the maximum eigenvalue of $A$ when $k$ tends to infinity.

3.   Algorithm

Based on Theorems 1–3, we can derive the algorithm for determining the maximum eigenvalue of a non-defective positive matrix.

Step 0. Given a non-defective positive matrix $A = {{\left({{a}_{ij}} \right)}_{n\times n}}$ and a sufficiently small positive number $\varepsilon\; > \; 0$;

Step 1. Let $\alpha = \underset{i}{\mathop{\max\limits}}\, \left\{ {{a}_{ii}} \right\}, \beta = \underset{i}{\mathop{\min\limits}}\, \left\{ {{a}_{ii}} \right\}$. Compute ${{B}_{1}} = {{\left(A+\alpha I \right)}^{n-1}}, {{B}_{2}} = {{\left(A-\beta I \right)}^{n-1}}$;

Step 2. Let $k = 0$;

Step 3. Compute $T = \underset{i}{\mathop{\max\limits}}\, \sqrt{\dfrac{{{r}_{i}}\left({{A}^{k+2}}{{B}_{1}}{{B}_{2}} \right)}{{{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right)}}, t = \underset{i}{\mathop{\min\limits}}\, \sqrt{\dfrac{{{r}_{i}}\left({{A}^{k+2}}{{B}_{1}}{{B}_{2}} \right)}{{{r}_{i}}\left({{A}^{k}}{{B}_{1}}{{B}_{2}} \right)}}$;

Step 4. If $T-t < \varepsilon$, go to Step 5; otherwise, set $k = k+1$ and go back to Step 3;

Step 5. Output $k$ and $\rho \left(A \right) = \dfrac{T+t}{2}$, stop.

Remark 3. Replace the row sums in the algorithm with the corresponding column sums. The algorithm is still valid.

Remark 4. In the above algorithm, the upper bound of $\rho \left(A \right)$ is decreasing, while the lower bound of $\rho \left(A \right)$ is increasing. This behavior exhibits a smoothing tendency and, as a result, we refer to this algorithm as a smoothing algorithm.

4.   Numerical examples

In this section, we consider two examples to demonstrate our findings.

Example 1. Consider positive matrix:

The comparisons between the estimation results of ^{[1,2,3,4,5,6,7,8]} and Theorem 1 of this paper regarding the maximal eigenvalue of matrix $A$ are presented in Table 1.

Indeed, $\rho(A) = 5.74165738\cdots$. The computational results in Table 1 demonstrate that the conclusions obtained from Theorem 1 in this paper improve upon the existing related results.

Example 2. Calculate the maximal eigenvalue of the non-defective positive matrix $B$ using the algorithm in Section 3. The results are presented in Table 2.

5.   Conclusions

In this paper, we have introduced monotonically increasing lower-bound estimators and monotonically decreasing upper-bound estimators for the maximal eigenvalue of a positive matrix. These estimators are constructed using two special matrices associated with the positive matrix. The advantage of these estimators is that they are straightforward to compute, as they solely depend on the elements of the positive matrix. Furthermore, we have rigorously proven the monotonicity and convergence of both the upper and lower bound estimations for the maximal eigenvalue of positive matrices.

Additionally, we have developed a smoothing algorithm specifically designed to calculate the approximate value of the maximal eigenvalue for a non-defective positive matrix. This algorithm serves as an effective tool to obtain a reasonably accurate estimate for the maximal eigenvalue in such cases.

Overall, our findings provide valuable insights and practical tools for estimating and computing the maximal eigenvalue of positive matrices, with special attention given to non-defective positive matrices.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work was financially supported by Sichuan University Jinjiang College Cultivation Project of Sichuan Higher Education Institutions of Double First-class Construction Gongga Plan.

Conflict of interest

The authors declare that they have no competing interests.