ALGEBRAIC COMBINATORICS

no. 1
Isospectral reductions and quantum walks on graphs
Kempton, Mark1; Tolbert, John2
1 Brigham Young University Department of Mathematics Provo UT 84602 (USA)
2 Wake Forest University Department of Mathematics Winston-Salem NC 27587 (USA)
Algebraic Combinatorics, Volume 7 (2024) no. 1, pp. 225-243.

We give a new formula for computing the isospectral reduction of a matrix (and graph) down to a submatrix (or subgraph). Using this, we generalize the notion of isospectral reductions. In addition, we give a procedure for constructing a matrix whose isospectral reduction down to a submatrix is given. We also prove that the isospectral reduction completely determines the restriction of the quantum walk transition matrix to a subset. Using these, we construct new families of simple graphs exhibiting perfect quantum state transfer.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.333
Classification: 05C50, 15A18
Keywords: isospectral reduction, equitable partition, quantum walk, perfect state transfer
Kempton, Mark 1; Tolbert, John 2

1 Brigham Young University Department of Mathematics Provo UT 84602 (USA)
2 Wake Forest University Department of Mathematics Winston-Salem NC 27587 (USA)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2024__7_1_225_0,
     author = {Kempton, Mark and Tolbert, John},
     title = {Isospectral reductions and quantum walks on graphs},
     journal = {Algebraic Combinatorics},
     pages = {225--243},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {1},
     year = {2024},
     doi = {10.5802/alco.333},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.333/}
}
TY  - JOUR
AU  - Kempton, Mark
AU  - Tolbert, John
TI  - Isospectral reductions and quantum walks on graphs
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 225
EP  - 243
VL  - 7
IS  - 1
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.333/
DO  - 10.5802/alco.333
LA  - en
ID  - ALCO_2024__7_1_225_0
ER  - 
%0 Journal Article
%A Kempton, Mark
%A Tolbert, John
%T Isospectral reductions and quantum walks on graphs
%J Algebraic Combinatorics
%D 2024
%P 225-243
%V 7
%N 1
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.333/
%R 10.5802/alco.333
%G en
%F ALCO_2024__7_1_225_0
Kempton, Mark; Tolbert, John. Isospectral reductions and quantum walks on graphs. Algebraic Combinatorics, Volume 7 (2024) no. 1, pp. 225-243. doi : 10.5802/alco.333. https://alco.centre-mersenne.org/articles/10.5802/alco.333/

[1] Brauer, Alfred Limits for the characteristic roots of a matrix. II, Duke Math. J., Volume 14 (1947), pp. 21-26 http://projecteuclid.org/euclid.dmj/1077473986 | MR | Zbl

[2] Brualdi, Richard A. Matrices, eigenvalues, and directed graphs, Linear and Multilinear Algebra, Volume 11 (1982) no. 2, pp. 143-165 | DOI | MR | Zbl

[3] Bunimovich, L. A.; Webb, B. Z. Isospectral graph transformations, spectral equivalence, and global stability of dynamical networks, Nonlinearity, Volume 25 (2012) no. 1, pp. 211-254 | DOI | MR | Zbl

[4] Bunimovich, L. A.; Webb, B. Z. Restrictions and stability of time-delayed dynamical networks, Nonlinearity, Volume 26 (2013) no. 8, pp. 2131-2156 | DOI | MR | Zbl

[5] Bunimovich, L. A.; Webb, B. Z. Improved estimates of survival probabilities via isospectral transformations, Springer Proc. Math. Stat., 70, Springer, New York, 2014, pp. 119-135 | DOI | MR

[6] Bunimovich, L. A.; Webb, B. Z. Isospectral transformations: A new approach to analyzing multidimensional systems and networks, Springer Monographs in Mathematics, Springer, New York, 2014, xvi+175 pages | DOI | MR

[7] Chan, Ada; Coutinho, Gabriel; Drazen, Whitney; Eisenberg, Or; Godsil, Chris; Kempton, Mark; Lippner, Gabor; Tamon, Christino; Zhan, Hanmeng Fundamentals of fractional revival in graphs, Linear Algebra Appl., Volume 655 (2022), pp. 129-158 | DOI | MR | Zbl

[8] Chan, Ada; Coutinho, Gabriel; Tamon, Christino; Vinet, Luc; Zhan, Hanmeng Quantum fractional revival on graphs, Discrete Appl. Math., Volume 269 (2019), pp. 86-98 | DOI | MR | Zbl

[9] Chan, Ada; Drazen, Whitney; Eisenberg, Or; Kempton, Mark; Lippner, Gabor Pretty good quantum fractional revival in paths and cycles, Algebr. Comb., Volume 4 (2021) no. 6, pp. 989-1004 | DOI | Numdam | MR | Zbl

[10] Doetsch, Gustav Introduction to the theory and application of the Laplace transformation, Springer-Verlag, New York-Heidelberg, 1974, vii+326 pages | DOI | MR

[11] Duarte, Pedro; Torres, Maria Joana Eigenvectors of isospectral graph transformations, Linear Algebra Appl., Volume 474 (2015), pp. 110-123 | DOI | MR | Zbl

[12] Gershgorin, S. Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk SSSR Ser. Mat., Volume 1 (1931), pp. 749-754 | Zbl

[13] Godsil, Chris State transfer on graphs, Discrete Math., Volume 312 (2012) no. 1, pp. 129-147 | DOI | MR | Zbl

[14] Godsil, Chris; Kirkland, Stephen; Severini, Simone; Smith, Jamie Number-Theoretic Nature of Communication in Quantum Spin Systems, Phys. Rev. Lett., Volume 109 (2012), Paper no. 050502, 4 pages https://link.aps.org/doi/10.1103/PhysRevLett.109.050502 | DOI

[15] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | DOI | MR

[16] Guevara Vasquez, Fernando; Webb, Benjamin Z. Pseudospectra of isospectrally reduced matrices, Numer. Linear Algebra Appl., Volume 22 (2015) no. 1, pp. 145-174 | DOI | MR | Zbl

[17] Kay, Alastair Perfect, efficient, state transfer and its application as a constructive tool, Int. J. Quantum Inf., Volume 08 (2010) no. 04, pp. 641-676 | DOI | Zbl

[18] Kempton, Mark; Sinkovic, John; Smith, Dallas; Webb, Benjamin Characterizing cospectral vertices via isospectral reduction, Linear Algebra Appl., Volume 594 (2020), pp. 226-248 | DOI | MR | Zbl

[19] Morfonios, C. V.; Pyzh, M.; Röntgen, M.; Schmelcher, P. Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices, Linear Algebra Appl., Volume 624 (2021), pp. 53-86 | DOI | MR | Zbl

[20] Reber, David; Webb, Benjamin Intrinsic stability: stability of dynamical networks and switched systems with any type of time-delays, Nonlinearity, Volume 33 (2020) no. 6, pp. 2660-2685 | DOI | MR | Zbl

[21] Röntgen, M.; Palaiodimopoulos, N. E.; Morfonios, C. V.; Brouzos, I.; Pyzh, M.; Diakonos, F. K.; Schmelcher, P. Designing pretty good state transfer via isospectral reductions, Phys. Rev. A, Volume 101 (2020), Paper no. 042304, 20 pages | DOI | MR

Cited by Sources: