Eigenvectors and controllability of non-Hermitian random matrices and directed graphs. (English) Zbl 1470.15033
The authors study the eigenvectors and the eigenvalues of random matrices with i.i.d. entries that have a symmetric distribution. The main results provide a small ball probability bound for the linear combinations of the associated coordinates. They also provide an optimal estimate of the probability that an i.i.d. matrix has simple spectrum. Their techniques establish analogous results for the adjacency matrix of a random directed graph, and as an application, establish some controllability properties of network systems on directed graphs.
Reviewer: George Stoica (Saint John)
MSC:
| 15B52 | Random matrices (algebraic aspects) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 60B20 | Random matrices (probabilistic aspects) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 93E03 | Stochastic systems in control theory (general) |
References:
| [1] | C. O. Aguilar and B. Gharesifard. Graph controllability classes for the Laplacian leader-follower dynamics. IEEE Trans. Automat. Control, 60(6):1611-1623, 2015. · Zbl 1360.93085 |
| [2] | C. O. Aguilar and B. Gharesifard. Laplacian controllability classes for threshold graphs. Linear Algebra Appl., 471:575-586, 2015. · Zbl 1307.05135 |
| [3] | R. Allez and J.-P. Bouchaud. Eigenvector dynamics under free addition. Random Matrices Theory Appl., 3(3):1450010, 17, 2014. · Zbl 1301.60008 |
| [4] | G. B. Arous, P. Bourgade, et al. Extreme gaps between eigenvalues of random matrices. The Annals of Probability, 41(4):2648-2681, 2013. · Zbl 1282.60008 |
| [5] | A. Athreya, C. E. Priebe, M. Tang, V. Lyzinski, D. J. Marchette, and D. L. Sussman. A limit theorem for scaled eigenvectors of random dot product graphs. Sankhya A, 78(1):1-18, 2016. · Zbl 1338.62061 |
| [6] | Z. D. Bai, B. Q. Miao, and G. M. Pan. On asymptotics of eigenvectors of large sample covariance matrix. Ann. Probab., 35(4):1532-1572, 2007. · Zbl 1162.15012 |
| [7] | A. Basak and M. Rudelson. Invertibility of sparse non-Hermitian matrices. Adv. Math., 310:426-483, 2017. · Zbl 1406.60013 |
| [8] | V. Belevitch. Classical network theory. Holden-Day, San Francisco, Calif.-Cambridge-Amsterdam, 1968. · Zbl 0172.20404 |
| [9] | S. Belinschi, M. A. Nowak, R. Speicher, and W. Tarnowski. Squared eigenvalue condition numbers and eigenvector correlations from the single ring theorem. J. Phys. A, 50(10):105204, 11, 2017. · Zbl 1361.81051 |
| [10] | F. Benaych-Georges. A universality result for the global fluctuations of the eigenvectors of Wigner matrices. Random Matrices Theory Appl., 1(4):1250011, 23, 2012. · Zbl 1266.15046 |
| [11] | F. Benaych-Georges and A. Guionnet. Central limit theorem for eigenvectors of heavy tailed matrices. Electron. J. Probab., 19:no. 54, 27, 2014. · Zbl 1293.15021 |
| [12] | F. Benaych-Georges and R. R. Nadakuditi. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices. Adv. Math., 227(1):494-521, 2011. · Zbl 1226.15023 |
| [13] | F. Benaych-Georges and S. Péché. Largest eigenvalues and eigenvectors of band or sparse random matrices. Electron. Commun. Probab., 19:no. 4, 9, 2014. · Zbl 1297.15038 |
| [14] | F. Benaych-Georges and O. Zeitouni. Eigenvectors of non normal random matrices. Available at 1806.06806, 2018. · Zbl 1403.15029 |
| [15] | A. Bloemendal, L. Erdős, A. Knowles, H.-T. Yau, and J. Yin. Isotropic local laws for sample covariance and generalized Wigner matrices. Electron. J. Probab., 19:no. 33, 53, 2014. · Zbl 1288.15044 |
| [16] | C. Bordenave and A. Guionnet. Localization and delocalization of eigenvectors for heavy-tailed random matrices. Probab. Theory Related Fields, 157(3-4):885-953, 2013. · Zbl 1296.15019 |
| [17] | P. Bourgade and G. Dubach. The distribution of overlaps between eigenvectors of ginibre matrices. Available at 1801.01219, 2018. · Zbl 1451.60015 |
| [18] | P. Bourgade, J. Huang, and H.-T. Yau. Eigenvector statistics of sparse random matrices. Electron. J. Probab., 22:Paper No. 64, 38, 2017. · Zbl 1372.05195 |
| [19] | P. Bourgade and H.-T. Yau. The eigenvector moment flow and local quantum unique ergodicity. Comm. Math. Phys., 350(1):231-278, 2017. · Zbl 1379.58014 |
| [20] | J. Bourgain, V. H. Vu, and P. M. Wood. On the singularity probability of discrete random matrices. Journal of Functional Analysis, 258(2):559-603, 2010. · Zbl 1186.60003 |
| [21] | J. T. Chalker and B. Mehlig. Eigenvector statistics in non-hermitian random matrix ensembles. Phys. Rev. Lett., 81:3367-3370, Oct 1998. |
| [22] | K. P. Costello, T. Tao, V. Vu, et al. Random symmetric matrices are almost surely nonsingular. Duke Mathematical Journal, 135(2):395-413, 2006. · Zbl 1110.15020 |
| [23] | N. Crawford and R. Rosenthal. Eigenvector correlations in the complex ginibre ensemble. Available at 1805.08993, 2018. |
| [24] | Y. Dekel, J. R. Lee, and N. Linial. Eigenvectors of random graphs: nodal domains. Random Structures Algorithms, 39(1):39-58, 2011. · Zbl 1223.05275 |
| [25] | I. Dumitriu and S. Pal. Sparse regular random graphs: spectral density and eigenvectors. Ann. Probab., 40(5):2197-2235, 2012. · Zbl 1255.05173 |
| [26] | A. Edelman. Eigenvalues and condition numbers of random matrices. SIAM journal on matrix analysis and applications, 9(4):543-560, 1988. · Zbl 0678.15019 |
| [27] | R. Eldan, M. Z. Rácz, and T. Schramm. Braess’s paradox for the spectral gap in random graphs and delocalization of eigenvectors. Random Structures Algorithms, 50(4):584-611, 2017. · Zbl 1368.05132 |
| [28] | L. Erdős and A. Knowles. Quantum diffusion and delocalization for band matrices with general distribution. Ann. Henri Poincaré, 12(7):1227-1319, 2011. · Zbl 1247.15033 |
| [29] | L. Erdős and A. Knowles. Quantum diffusion and eigenfunction delocalization in a random band matrix model. Comm. Math. Phys., 303(2):509-554, 2011. · Zbl 1226.15024 |
| [30] | L. Erdős, A. Knowles, H.-T. Yau, and J. Yin. Delocalization and diffusion profile for random band matrices. Comm. Math. Phys., 323(1):367-416, 2013. · Zbl 1279.15027 |
| [31] | L. Erdős, B. Schlein, and H.-T. Yau. Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices. Ann. Probab., 37(3):815-852, 2009. · Zbl 1175.15028 |
| [32] | L. Erdős, H.-T. Yau, and J. Yin. Bulk universality for generalized Wigner matrices. Probab. Theory Related Fields, 154(1-2):341-407, 2012. · Zbl 1277.15026 |
| [33] | A. Ferber and V. Jain. Singularity of random symmetric matrices—a combinatorial approach to improved bounds. In Forum of Mathematics, Sigma, volume 7. Cambridge University Press, 2019. · Zbl 1423.60016 |
| [34] | A. Ferber, V. Jain, K. Luh, and W. Samotij. On the counting problem in inverse littlewood-offord theory. arXiv preprint 1904.10425, 2019. |
| [35] | D. A. Ford and C. D. Johnson. Invariant subspaces and the controllability and observability of linear dynamical systems. SIAM J. Control, 6:553-558, 1968. · Zbl 0188.48701 |
| [36] | Y. V. Fyodorov. On statistics of bi-orthogonal eigenvectors in real and complex Ginibre ensembles: combining partial Schur decomposition with supersymmetry. Comm. Math. Phys., 363(2):579-603, 2018. · Zbl 1448.60022 |
| [37] | S. Ge. The Eigenvalue Spacing of IID Random Matrices and Related Least Singular Value Results. PhD thesis, UCLA, 2017. |
| [38] | L. Geisinger. Convergence of the density of states and delocalization of eigenvectors on random regular graphs. J. Spectr. Theory, 5(4):783-827, 2015. · Zbl 1384.60024 |
| [39] | E. G. Gilbert. Controllability and observability in multivariable control systems. J. SIAM Control Ser. A, 1:128-151 (1963), 1963. · Zbl 0143.12401 |
| [40] | C. Godsil. Controllable subsets in graphs. Ann. Comb., 16(4):733-744, 2012. · Zbl 1256.05139 |
| [41] | A. J. Graham and D. A. Pike. A note on thresholds and connectivity in random directed graphs. Atl. Electron. J. Math., 3(1):1-5, 2008. · Zbl 1291.05186 |
| [42] | M. L. J. Hautus. Controllability and observability conditions of linear autonomous systems. Nederl. Akad. Wetensch. Proc. Ser. A 72 = Indag. Math., 31:443-448, 1969. · Zbl 0188.46801 |
| [43] | V. Jain. Approximate spielman-teng theorems for random matrices with heavy-tailed entries: a combinatorial view. arXiv preprint 1904.11108, 2019. |
| [44] | C. D. Johnson. Invariant hyperplanes for linear dynamical systems. IEEE Trans. Automatic Control, AC-11:113-116, 1966. |
| [45] | J. Kahn, J. Komlós, and E. Szemerédi. On the probability that a random±1-matrix is singular. Journal of the American Mathematical Society, 8(1):223-240, 1995. · Zbl 0829.15018 |
| [46] | T. Kailath. Linear systems. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Information and System Sciences Series. · Zbl 0454.93001 |
| [47] | R. E. Kalman. Lectures on controllability and observability. In Controllability and Observability (C.I.M.E. 1st Ciclo, Sasso Marconi (Bologna), 1968), pages 1-149. Edizioni Cremonese, Rome, 1969. · Zbl 0208.17201 |
| [48] | A. Knowles and J. Yin. Eigenvector distribution of Wigner matrices. Probab. Theory Related Fields, 155(3-4):543-582, 2013. · Zbl 1268.15033 |
| [49] | J. Komlós. On determinant of (0, 1) matrices. Studia Science Mathematics Hungarica, 2:7-21, 1967. · Zbl 0153.05002 |
| [50] | J. O. Lee and K. Schnelli. Extremal eigenvalues and eigenvectors of deformed Wigner matrices. Probab. Theory Related Fields, 164(1-2):165-241, 2016. · Zbl 1338.15071 |
| [51] | A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann, and P. Youssef. Structure of eigenvectors of random regular digraphs. Trans. Amer. Math. Soc., 371(11):8097-8172, 2019. · Zbl 1447.05091 |
| [52] | Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási. Controllability of complex networks. Nature, 473(7346):167-173, 2011. |
| [53] | P. Lopatto and K. Luh. Tail bounds for gaps between eigenvalues of sparse random matrices. arXiv preprint 1901.05948, 2019. |
| [54] | Y. Lou and Y. Hong. Controllability analysis of multi-agent systems with directed and weighted interconnection. Internat. J. Control, 85(10):1486-1496, 2012. · Zbl 1253.93012 |
| [55] | K. Luh. Complex random matrices have no real eigenvalues. Random Matrices Theory Appl., 7(1):1750014, 17, 2018. · Zbl 1390.60033 |
| [56] | K. Luh and S. O’Rourke. Eigenvector delocalization for non-hermitian random matrices and applications. arXiv preprint 1810.00489, 2018. |
| [57] | K. Luh and V. Vu. Sparse random matrices have simple spectrum. arXiv preprint 1802.03662, 2018. · Zbl 1465.60011 |
| [58] | A. Lytova and K. Tikhomirov. On delocalization of eigenvectors of random non-hermitian matrices. Availabe at 1810.01590, 2018. · Zbl 1458.15061 |
| [59] | S. Meehan and H. Nguyen. Eigenvectors of random matrices of symmetric entry distributions. Proc. Amer. Math. Soc., 147(2):835-847, 2019. · Zbl 1439.60011 |
| [60] | B. Mehlig and J. T. Chalker. Statistical properties of eigenvectors in non-Hermitian Gaussian random matrix ensembles. J. Math. Phys., 41(5):3233-3256, 2000. · Zbl 0977.82023 |
| [61] | P. Mitra. Entrywise bounds for eigenvectors of random graphs. Electron. J. Combin., 16(1):Research Paper 131, 18, 2009. · Zbl 1186.05109 |
| [62] | M. Nabi-Abdolyousefi. Controllability, identification, and randomness in distributed systems. Springer Theses. Springer, Cham, 2014. Doctoral thesis accepted by the University of Washington, Washington, USA. · Zbl 1352.93007 |
| [63] | M. Nabi-Abdolyousefi and M. Mesbahi. On the controllability properties of circulant networks. IEEE Trans. Automat. Control, 58(12):3179-3184, 2013. · Zbl 1369.93086 |
| [64] | H. Nguyen, T. Tao, and V. Vu. Random matrices: tail bounds for gaps between eigenvalues. Probab. Theory Related Fields, 167(3-4):777-816, 2017. · Zbl 1391.15111 |
| [65] | H. H. Nguyen et al. Inverse littlewood-offord problems and the singularity of random symmetric matrices. Duke Mathematical Journal, 161(4):545-586, 2012. · Zbl 1276.15019 |
| [66] | S. O’Rourke and D. Renfrew. Low rank perturbations of large elliptic random matrices. Electron. J. Probab., 19:no. 43, 65, 2014. · Zbl 1315.60008 |
| [67] | S. O’Rourke and B. Touri. Controllability of random systems: Universality and minimal controllability. Available at 1506.03125, 2015. |
| [68] | S. O’Rourke and B. Touri. Littlewood-offord theory and controllability of random structures. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 5195-5200, Dec 2016. |
| [69] | S. O’Rourke and B. Touri. On a conjecture of Godsil concerning controllable random graphs. SIAM J. Control Optim., 54(6):3347-3378, 2016. · Zbl 1352.93027 |
| [70] | S. O’Rourke, V. Vu, and K. Wang. Eigenvectors of random matrices: a survey. J. Combin. Theory Ser. A, 144:361-442, 2016. · Zbl 1347.15044 |
| [71] | V.-M. Popov. Hyperstability of control systems. Editura Academiei, Bucharest; Springer-Verlag, Berlin-New York, 1973. Translated from the Romanian by Radu Georgescu, Die Grundlehren der mathematischen Wissenschaften, Band 204. · Zbl 0276.93033 |
| [72] | A. Rahmani, M. Ji, M. Mesbahi, and M. Egerstedt. Controllability of multi-agent systems from a graph-theoretic perspective. SIAM J. Control Optim., 48(1):162-186, 2009. · Zbl 1182.93025 |
| [73] | E. Rebrova and K. Tikhomirov. Coverings of random ellipsoids, and invertibility of matrices with iid heavy-tailed entries. Israel Journal of Mathematics, 227(2):507-544, 2018. · Zbl 1405.60012 |
| [74] | B. A. Rogozin. On the increase of dispersion of sums of independent random variables. Teor. Verojatnost. i Primenen, 6:106-108, 1961. · Zbl 0106.34003 |
| [75] | H. H. Rosenbrock. State-space and multivariable theory. John Wiley & Sons, Inc. [Wiley Interscience Division], New York, 1970. · Zbl 0246.93010 |
| [76] | M. Rudelson. Delocalization of eigenvectors of random matrices. lecture notes. Available at 1707.08461, 2017. |
| [77] | M. Rudelson and R. Vershynin. The Littlewood-Offord problem and invertibility of random matrices. Adv. Math., 218(2):600-633, 2008. · Zbl 1139.15015 |
| [78] | M. Rudelson and R. Vershynin. Smallest singular value of a random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707-1739, 2009. · Zbl 1183.15031 |
| [79] | M. Rudelson and R. Vershynin. Delocalization of eigenvectors of random matrices with independent entries. Duke Math. J., 164(13):2507-2538, 2015. · Zbl 1352.60007 |
| [80] | M. Rudelson and R. Vershynin. No-gaps delocalization for general random matrices. Geom. Funct. Anal., 26(6):1716-1776, 2016. · Zbl 1375.60027 |
| [81] | J. Schenker. Eigenvector localization for random band matrices with power law band width. Comm. Math. Phys., 290(3):1065-1097, 2009. · Zbl 1179.82079 |
| [82] | D. Shi and Y. Jiang. Smallest gaps between eigenvalues of random matrices with complex ginibre, wishart and universal unitary ensembles. arXiv preprint 1207.4240, 2012. |
| [83] | J. W. Silverstein. On the eigenvectors of large-dimensional sample covariance matrices. J. Multivariate Anal., 30(1):1-16, 1989. · Zbl 0678.60011 |
| [84] | F. Slanina. Localization of eigenvectors in random graphs. Eur. Phys. J. B, 85(11):Art. 361, 12, 2012. · Zbl 1515.05162 |
| [85] | D. A. Spielman and S.-H. Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):385-463, 2004. · Zbl 1192.90120 |
| [86] | H. G. Tanner. On the controllability of nearest neighbor interconnections. In 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No.04CH37601), volume 3, pages 2467-2472 Vol.3, Dec 2004. |
| [87] | T. Tao and V. Vu. On random±1 matrices: singularity and determinant. Random Structures & Algorithms, 28(1):1-23, 2006. · Zbl 1086.60008 |
| [88] | T. Tao and V. Vu. Smooth analysis of the condition number and the least singular value. Mathematics of computation, 79(272):2333-2352, 2010. · Zbl 1253.65067 |
| [89] | T. Tao and V. Vu. Random matrices: universal properties of eigenvectors. Random Matrices Theory Appl., 1(1):1150001, 27, 2012. · Zbl 1248.15031 |
| [90] | T. Tao and V. Vu. Random matrices have simple spectrum. Combinatorica, 37(3):539-553, 2017. · Zbl 1399.60008 |
| [91] | T. Tao and V. H. Vu. Inverse littlewood-offord theorems and the condition number of random discrete matrices. Annals of Mathematics, pages 595-632, 2009. · Zbl 1250.60023 |
| [92] | K. Tikhomirov. Singularity of random bernoulli matrices. Annals of Mathematics, 191(2):593-634, 2020. · Zbl 1458.15023 |
| [93] | K. Truong and A. Ossipov. Statistics of eigenvectors in the deformed Gaussian unitary ensemble of random matrices. J. Phys. A, 49(14):145005, 11, 2016. · Zbl 1342.81129 |
| [94] | K. Truong and A. Ossipov. Statistical properties of eigenvectors and eigenvalues of structured random matrices. J. Phys. A, 51(6):065001, 12, 2018. · Zbl 1383.15036 |
| [95] | R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed sensing, pages 210-268. Cambridge Univ. Press, Cambridge, 2012. |
| [96] | R. Vershynin. Invertibility of symmetric random matrices. Random Structures Algorithms, 44(2):135-182, 2014. · Zbl 1291.15088 |
| [97] | V. Vu and K. Wang. Random weighted projections, random quadratic forms and random eigenvectors. Random Structures Algorithms, 47(4):792-821, 2015. · Zbl 1384.60029 |
| [98] | Y. Q. Yin, Z. D. Bai, and P. R. Krishnaiah. On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix. Probab. Theory Related Fields, 78(4):509-521, 1988. · Zbl 0627.62022 |
| [99] | X. Zhan. Matrix theory, volume 147 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2013. · Zbl 1275.15001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
