American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2019097

Perron vector analysis for irreducible nonnegative tensors and its applications

Wen Li 1, , Wei-Hui Liu 2,, and  Seak Weng Vong 2,

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  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.

Keywords: Nonnegative tensor, Perron vector, irreducibility, spectral radius, bound.
Mathematics Subject Classification: Primary: 15A69.
Citation: Wen Li, Wei-Hui Liu, Seak Weng Vong. Perron vector analysis for irreducible nonnegative tensors and its applications. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019097
References:
[1]

K. Chang, K. 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.  Google Scholar

[2]

K. Chang, K. 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.  Google Scholar

[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.  Google Scholar

[4]

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

[5]

S. Friedland, S. 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.  Google Scholar

[6] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, UK, 1991.   Google Scholar
[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.  Google Scholar

[8]

W. Li, L. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[13]

Q. Liu, C. 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.  Google Scholar

[14]

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

[15]

M. Ng, L. 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.  Google Scholar

[16]

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

[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.  Google Scholar

[18]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

K. Chang, K. 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.  Google Scholar

[2]

K. Chang, K. 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.  Google Scholar

[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.  Google Scholar

[4]

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

[5]

S. Friedland, S. 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.  Google Scholar

[6] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, UK, 1991.   Google Scholar
[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.  Google Scholar

[8]

W. Li, L. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[13]

Q. Liu, C. 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.  Google Scholar

[14]

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

[15]

M. Ng, L. 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.  Google Scholar

[16]

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

[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.  Google Scholar

[18]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

Figure 1.  Comparison between two Ky Fan type Theorems
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The results of randomly constructed tensors
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The results of perturbation bounds (left) n = 5 and (right) n = 10
Figure Options

Download full-size image

Download as PowerPoint slide

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
Table Options

Download as excel

$ \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}} $
Table Options

Download as excel

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%
Table Options

Download as excel

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 & 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 & 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 & Related Fields, 2020, 10 (3) : 573-590. doi: 10.3934/mcrf.2020011
[4]

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

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
[6]

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

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

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

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
[10]

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

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

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
[13]

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

Daniel N. Dore, Andrew D. Hanlon. Area preserving maps on $\boldsymbol{S^2}$: A lower bound on the $\boldsymbol{C^0}$-norm using symplectic spectral invariants. Electronic Research Announcements, 2013, 20: 97-102. doi: 10.3934/era.2013.20.97
[15]

Guangsheng Wei, Hong-Kun Xu. On the missing bound state data of inverse spectral-scattering problems on the half-line. Inverse Problems & Imaging, 2015, 9 (1) : 239-255. doi: 10.3934/ipi.2015.9.239
[16]

Uri Bader, Roman Muchnik. Boundary unitary representations-irreducibility and rigidity. Journal of Modern Dynamics, 2011, 5 (1) : 49-69. doi: 10.3934/jmd.2011.5.49
[17]

Silvère Gangloff, Benjamin Hellouin de Menibus. Effect of quantified irreducibility on the computability of subshift entropy. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 1975-2000. doi: 10.3934/dcds.2019083
[18]

Kai Zehmisch. The codisc radius capacity. Electronic Research Announcements, 2013, 20: 77-96. doi: 10.3934/era.2013.20.77
[19]

Stefan Klus, Péter Koltai, Christof Schütte. On the numerical approximation of the Perron-Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (1) : 51-79. doi: 10.3934/jcd.2016003
[20]

Eric Férard. On the irreducibility of the hyperplane sections of Fermat varieties in $\mathbb{P}^3$ in characteristic $2$. Advances in Mathematics of Communications, 2014, 8 (4) : 497-509. doi: 10.3934/amc.2014.8.497

2019 Impact Factor: 1.366

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences