January  2021, 17(1): 29-50. doi: 10.3934/jimo.2019097

Perron vector analysis for irreducible nonnegative tensors and its applications

1. 

School of Mathematical Sciences, South China Normal University, Guangzhou 510631, China

2. 

Department of Mathematics, University of Macau, Macau, China

* Corresponding author: Wei-Hui Liu

Received  January 2019 Revised  March 2019 Published  January 2021 Early access  July 2019

Fund Project: The first author is supported by NSFC grant 11671158, U1811464 and 11771159. The second author is supported by NSFC grant 11571124 and UM grant MYRG2016-00077-FST. The third author is supported by UM grant MYRG2017-00098-FST

In this paper, we analyse the Perron vector of an irreducible nonnegative tensor, and present some lower and upper bounds for the ratio of the smallest and largest entries of a Perron vector based on some new techniques, which always improve the existing ones. Applying these new ratio results, we first refine two-sided bounds for the spectral radius of an irreducible nonnegative tensor. In particular, for the matrix case, the new bounds also improve the corresponding ones. Second, we provide a new Ky Fan type theorem, which improves the existing one. Third, we refine the perturbation bound for the spectral radii of nonnegative tensors, from which one may derive a comparison theorem for spectral radii of nonnegative tensors. Numerical examples are given to show the efficiency of the theoretical results.

Citation: Wen Li, Wei-Hui Liu, Seak Weng Vong. Perron vector analysis for irreducible nonnegative tensors and its applications. Journal of Industrial and Management Optimization, 2021, 17 (1) : 29-50. doi: 10.3934/jimo.2019097
References:
[1]

K. ChangK. Pearson and T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci., 6 (2008), 507-520.  doi: 10.4310/CMS.2008.v6.n2.a12.

[2]

K. ChangK. Pearson and T. Zhang, Primitivity, the convergence of the NQZ method, and the largest eigenvalue for nonnegative tensors, SIAM J. Matrix Anal. Appl., 33 (2011), 806-819.  doi: 10.1137/100807120.

[3]

K. Chang and T. Zhang, On the uniqueness and non-uniqueness of the positive $Z$-eigenvector for transition probability tensors, J. Math. Anal. Appl., 408 (2013), 525-540.  doi: 10.1016/j.jmaa.2013.04.019.

[4]

L. De LathauwerB. De Moor and J. Vandewalle, A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21 (2000), 1253-1278.  doi: 10.1137/S0895479896305696.

[5]

S. FriedlandS. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl., 438 (2013), 738-749.  doi: 10.1016/j.laa.2011.02.042.

[6] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, UK, 1991. 
[7]

S. Hu and L. Qi, Algebraic connectivity of an even uniform hypergraph, J. Comb. Optim., 24 (2012), 564-579.  doi: 10.1007/s10878-011-9407-1.

[8]

W. LiL. B. Cui and M. Ng, The perturbation bound for the Perron vector of a transition probability tensor, Numer. Linear Algebra Appl., 20 (2013), 985-1000.  doi: 10.1002/nla.1886.

[9]

W. Li and M. Ng, On the limiting probability distribution of a transition probability tensor, Linear Multilin. Algebra, 62 (2014), 362-385.  doi: 10.1080/03081087.2013.777436.

[10]

W. Li and M. K. Ng, The perturbation bound for the spectral radius of a nonnegative tensor, Adv. Numer. Anal., 2014 (2014), 10pp. doi: 10.1155/2014/109525.

[11]

W. Li and M. K. Ng, Some bounds for the spectral radius of nonnegative tensors, Numer. Math., 130 (2015), 315-335.  doi: 10.1007/s00211-014-0666-5.

[12]

L. H. Lim, Singular values and eigenvalues of tensors: A variational approach, in Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 05, vol. 1, IEEE Computer Society Press, Piscataway, NJ, 2005, 129-132.

[13]

Q. LiuC. Li and C. Zhang, Some inequalities on the Perron eigenvalue and eigenvectors for positive tensors, J. of Math. Inequal., 10 (2016), 405-414.  doi: 10.7153/jmi-10-31.

[14]

H. Minc, Nonnegative Matrices, John Wiley & Sons, New York, 1988.

[15]

M. NgL. Qi and G. Zhou, Finding the largest eigenvalue of a non-negative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099.  doi: 10.1137/09074838X.

[16]

K. Pearson, Essentially positive tensors, Int. J. Algebra, 4 (2010), 421-426. 

[17]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. of Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.

[18]

L. Qi, Symmetric nonnegative tensor and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015.

[19]

L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, Society for Industrial and Applied Mathematics, Pennsylvania, 2017. doi: 10.1137/1.9781611974751.ch1.

[20]

Z. Wang and W. Wu, Bounds for the greatest eigenvalue of positive tensors, J. of Indust. and Mgmt. Optim., 10 (2014), 1031-1039.  doi: 10.3934/jimo.2014.10.1031.

[21]

Y. N. Yang and Q. Z. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors, SIAM J. Matrix Anal. Appl., 31 (2010), 2517-2530.  doi: 10.1137/090778766.

[22]

Q. Z. Yang and Y. N. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors Ⅱ, SIAM J. Matrix Anal. Appl., 32 (2011), 1236-1250.  doi: 10.1137/100813671.

show all references

References:
[1]

K. ChangK. Pearson and T. Zhang, Perron-Frobenius theorem for nonnegative tensors, Commun. Math. Sci., 6 (2008), 507-520.  doi: 10.4310/CMS.2008.v6.n2.a12.

[2]

K. ChangK. Pearson and T. Zhang, Primitivity, the convergence of the NQZ method, and the largest eigenvalue for nonnegative tensors, SIAM J. Matrix Anal. Appl., 33 (2011), 806-819.  doi: 10.1137/100807120.

[3]

K. Chang and T. Zhang, On the uniqueness and non-uniqueness of the positive $Z$-eigenvector for transition probability tensors, J. Math. Anal. Appl., 408 (2013), 525-540.  doi: 10.1016/j.jmaa.2013.04.019.

[4]

L. De LathauwerB. De Moor and J. Vandewalle, A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21 (2000), 1253-1278.  doi: 10.1137/S0895479896305696.

[5]

S. FriedlandS. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra Appl., 438 (2013), 738-749.  doi: 10.1016/j.laa.2011.02.042.

[6] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, UK, 1991. 
[7]

S. Hu and L. Qi, Algebraic connectivity of an even uniform hypergraph, J. Comb. Optim., 24 (2012), 564-579.  doi: 10.1007/s10878-011-9407-1.

[8]

W. LiL. B. Cui and M. Ng, The perturbation bound for the Perron vector of a transition probability tensor, Numer. Linear Algebra Appl., 20 (2013), 985-1000.  doi: 10.1002/nla.1886.

[9]

W. Li and M. Ng, On the limiting probability distribution of a transition probability tensor, Linear Multilin. Algebra, 62 (2014), 362-385.  doi: 10.1080/03081087.2013.777436.

[10]

W. Li and M. K. Ng, The perturbation bound for the spectral radius of a nonnegative tensor, Adv. Numer. Anal., 2014 (2014), 10pp. doi: 10.1155/2014/109525.

[11]

W. Li and M. K. Ng, Some bounds for the spectral radius of nonnegative tensors, Numer. Math., 130 (2015), 315-335.  doi: 10.1007/s00211-014-0666-5.

[12]

L. H. Lim, Singular values and eigenvalues of tensors: A variational approach, in Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 05, vol. 1, IEEE Computer Society Press, Piscataway, NJ, 2005, 129-132.

[13]

Q. LiuC. Li and C. Zhang, Some inequalities on the Perron eigenvalue and eigenvectors for positive tensors, J. of Math. Inequal., 10 (2016), 405-414.  doi: 10.7153/jmi-10-31.

[14]

H. Minc, Nonnegative Matrices, John Wiley & Sons, New York, 1988.

[15]

M. NgL. Qi and G. Zhou, Finding the largest eigenvalue of a non-negative tensor, SIAM J. Matrix Anal. Appl., 31 (2009), 1090-1099.  doi: 10.1137/09074838X.

[16]

K. Pearson, Essentially positive tensors, Int. J. Algebra, 4 (2010), 421-426. 

[17]

L. Qi, Eigenvalues of a real supersymmetric tensor, J. of Symbolic Comput., 40 (2005), 1302-1324.  doi: 10.1016/j.jsc.2005.05.007.

[18]

L. Qi, Symmetric nonnegative tensor and copositive tensors, Linear Algebra Appl., 439 (2013), 228-238.  doi: 10.1016/j.laa.2013.03.015.

[19]

L. Qi and Z. Luo, Tensor Analysis: Spectral Theory and Special Tensors, Society for Industrial and Applied Mathematics, Pennsylvania, 2017. doi: 10.1137/1.9781611974751.ch1.

[20]

Z. Wang and W. Wu, Bounds for the greatest eigenvalue of positive tensors, J. of Indust. and Mgmt. Optim., 10 (2014), 1031-1039.  doi: 10.3934/jimo.2014.10.1031.

[21]

Y. N. Yang and Q. Z. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors, SIAM J. Matrix Anal. Appl., 31 (2010), 2517-2530.  doi: 10.1137/090778766.

[22]

Q. Z. Yang and Y. N. Yang, Further results for Perron-Frobenius theorem for nonnegative tensors Ⅱ, SIAM J. Matrix Anal. Appl., 32 (2011), 1236-1250.  doi: 10.1137/100813671.

Figure 1.  Comparison between two Ky Fan type Theorems
Figure 2.  The results of randomly constructed tensors
Figure 3.  The results of perturbation bounds (left) n = 5 and (right) n = 10
Table 1.  Comparisons with the upper bounds for the ratio
$ \omega_1 $ in (3) $ \omega_2 $ in (4) $ \omega_3 $ in (5) $ \omega_4 $ in (11)
0.5575 0.5307 0.4855 0.5244
$ \omega_1 $ in (3) $ \omega_2 $ in (4) $ \omega_3 $ in (5) $ \omega_4 $ in (11)
0.5575 0.5307 0.4855 0.5244
Table 2.  Comparisons with the lower bounds for ratio
Example 2 Example 3 Example 4
Actual value of $ \frac{x_{\min}}{x_{\max}} $ 0.9873 0.6402 0.6794
$ \kappa_0 $ in (2) 0.6300 0.3969 0.5000
$ \kappa_1 $ in (3) 0.7857 0.2083 0.3077
$ \kappa_2 $ in (4) 0.5848 0.5000 0.4642
$ \kappa_3^{(1)} $ in (13) $ {\bf{0.9662}} $ 0.2808 0.3445
(t = -5.5602) (t = -5.7276) (t = -5.0250)
$ \kappa_3^{(2)} $ in (16) 0.9258 0.5000 $ {\bf{0.5539}} $
(also in (13)) (t = -5.1168) (t = -2.2315) (t = -2.2956)
$ \kappa_3^{(3)} $ in (13) 0.6300 $ {\bf{0.5724}} $ 0.5503
(t = -3.0000) (t = -3.5887) (t = -2.5208)
$ \kappa_3 $ in (13) $ {\bf{0.9662}} $ $ {\bf{0.5724}} $ $ {\bf{0.5539}} $
Example 2 Example 3 Example 4
Actual value of $ \frac{x_{\min}}{x_{\max}} $ 0.9873 0.6402 0.6794
$ \kappa_0 $ in (2) 0.6300 0.3969 0.5000
$ \kappa_1 $ in (3) 0.7857 0.2083 0.3077
$ \kappa_2 $ in (4) 0.5848 0.5000 0.4642
$ \kappa_3^{(1)} $ in (13) $ {\bf{0.9662}} $ 0.2808 0.3445
(t = -5.5602) (t = -5.7276) (t = -5.0250)
$ \kappa_3^{(2)} $ in (16) 0.9258 0.5000 $ {\bf{0.5539}} $
(also in (13)) (t = -5.1168) (t = -2.2315) (t = -2.2956)
$ \kappa_3^{(3)} $ in (13) 0.6300 $ {\bf{0.5724}} $ 0.5503
(t = -3.0000) (t = -3.5887) (t = -2.5208)
$ \kappa_3 $ in (13) $ {\bf{0.9662}} $ $ {\bf{0.5724}} $ $ {\bf{0.5539}} $
Table 3.  Comparisons between (20) and (27)
Dimension $ n = 5 $ $ n = 10 $ $ n = 15 $ $ n = 20 $
Lower bound 42.86% 64.02% 75.64% 81.37%
Upper bound 91.76% 94.50% 95.77% 96.83%
Dimension $ n = 5 $ $ n = 10 $ $ n = 15 $ $ n = 20 $
Lower bound 42.86% 64.02% 75.64% 81.37%
Upper bound 91.76% 94.50% 95.77% 96.83%
[1]

Chaoqian Li, Yaqiang Wang, Jieyi Yi, Yaotang Li. Bounds for the spectral radius of nonnegative tensors. Journal of Industrial and Management Optimization, 2016, 12 (3) : 975-990. doi: 10.3934/jimo.2016.12.975

[2]

Chen Ling, Liqun Qi. Some results on $l^k$-eigenvalues of tensor and related spectral radius. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 381-388. doi: 10.3934/naco.2011.1.381

[3]

Stéphane Gaubert, Nikolas Stott. A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices. Mathematical Control and Related Fields, 2020, 10 (3) : 573-590. doi: 10.3934/mcrf.2020011

[4]

Guimin Liu, Hongbin Lv. Bounds for spectral radius of nonnegative tensors using matrix-digragh-based approach. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021176

[5]

Vladimir Müller, Aljoša Peperko. On the Bonsall cone spectral radius and the approximate point spectrum. Discrete and Continuous Dynamical Systems, 2017, 37 (10) : 5337-5354. doi: 10.3934/dcds.2017232

[6]

Xiongping Dai, Yu Huang, Mingqing Xiao. Realization of joint spectral radius via Ergodic theory. Electronic Research Announcements, 2011, 18: 22-30. doi: 10.3934/era.2011.18.22

[7]

Rui Zou, Yongluo Cao, Gang Liao. Continuity of spectral radius over hyperbolic systems. Discrete and Continuous Dynamical Systems, 2018, 38 (8) : 3977-3991. doi: 10.3934/dcds.2018173

[8]

Vladimir Müller, Aljoša Peperko. Lower spectral radius and spectral mapping theorem for suprema preserving mappings. Discrete and Continuous Dynamical Systems, 2018, 38 (8) : 4117-4132. doi: 10.3934/dcds.2018179

[9]

Alberto Farina, Enrico Valdinoci. A pointwise gradient bound for elliptic equations on compact manifolds with nonnegative Ricci curvature. Discrete and Continuous Dynamical Systems, 2011, 30 (4) : 1139-1144. doi: 10.3934/dcds.2011.30.1139

[10]

Stefan Klus, Christof Schütte. Towards tensor-based methods for the numerical approximation of the Perron--Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (2) : 139-161. doi: 10.3934/jcd.2016007

[11]

Liqun Qi, Shenglong Hu, Yanwei Xu. Spectral norm and nuclear norm of a third order tensor. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1101-1113. doi: 10.3934/jimo.2021010

[12]

Victor Kozyakin. Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete and Continuous Dynamical Systems - B, 2010, 14 (1) : 143-158. doi: 10.3934/dcdsb.2010.14.143

[13]

Wen Jin, Horst R. Thieme. An extinction/persistence threshold for sexually reproducing populations: The cone spectral radius. Discrete and Continuous Dynamical Systems - B, 2016, 21 (2) : 447-470. doi: 10.3934/dcdsb.2016.21.447

[14]

Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042

[15]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021150

[16]

Luís Simão Ferreira. A lower bound for the spectral gap of the conjugate Kac process with 3 interacting particles. Kinetic and Related Models, 2022, 15 (1) : 91-117. doi: 10.3934/krm.2021045

[17]

Adela DePavia, Stefan Steinerberger. Spectral clustering revisited: Information hidden in the Fiedler vector. Foundations of Data Science, 2021, 3 (2) : 225-249. doi: 10.3934/fods.2021015

[18]

Victor Kozyakin. Minimax joint spectral radius and stabilizability of discrete-time linear switching control systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 3537-3556. doi: 10.3934/dcdsb.2018277

[19]

Daria Bugajewska, Mirosława Zima. On the spectral radius of linearly bounded operators and existence results for functional-differential equations. Conference Publications, 2003, 2003 (Special) : 147-155. doi: 10.3934/proc.2003.2003.147

[20]

Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (1) : 157-172. doi: 10.3934/jimo.2020147

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (349)
  • HTML views (1000)
  • Cited by (0)

Other articles
by authors

[Back to Top]