Perron vector analysis for irreducible nonnegative tensors and its applications

Wen Li; Wei-Hui Liu; Seak Weng Vong

doi:10.3934/jimo.2019097

Previous Article
A collaborative EPQ inventory model for a three-echelon supply chain with multiple products considering the effect of marketing effort on demand
JIMO Home
This Issue
Next Article
An imperfect sensing-based channel reservation strategy in CRNs and its performance evaluation

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
$ \kappa_3^{(1)} $ in (13)	(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
$ \kappa_3^{(3)} $ in (13)	(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
$ \kappa_3^{(1)} $ in (13)	(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
$ \kappa_3^{(3)} $ in (13)	(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]	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
[4]	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
[5]	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
[6]	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
[7]	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
[8]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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
[14]	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
[15]	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
[16]	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
[17]	Kai Zehmisch. The codisc radius capacity. Electronic Research Announcements, 2013, 20: 77-96. doi: 10.3934/era.2013.20.77
[18]	Jan Boman, Vladimir Sharafutdinov. Stability estimates in tensor tomography. Inverse Problems & Imaging, 2018, 12 (5) : 1245-1262. doi: 10.3934/ipi.2018052
[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

2018 Impact Factor: 1.025

Tools

Metrics

Tools

Article outline

Figures and Tables

2018 Impact Factor: 1.025

Tools

Figures and Tables

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences

Perron vector analysis for irreducible nonnegative tensors and its applications

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Perron vector analysis for irreducible nonnegative tensors and its applications

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors