Graphs associated with matrices over finite fields and their endomorphisms. (English) Zbl 1288.05158
Summary: Let \(\mathbb{F}^{m \times n}\) be the set of \(m \times n\) matrices over a field \(\mathbb{F}\). Consider a graph \(G = (\mathbb{F}^{m \times n}, \sim)\) with \(\mathbb{F}^{m \times n}\) as the vertex set such that two vertices \(A, B \in \mathbb{F}^{m \times n}\) are adjacent if \(\text{rank}(A - B) = 1\). We study graph properties of \(G\) when \(\mathbb{F}\) is a finite field. In particular, \(G\) is a regular connected graph with diameter equal to \(\min \{m, n \}\); it is always Hamiltonian. Furthermore, we determine the independence number, chromatic number and clique number of \(G\). These results are used to characterize the graph endomorphisms of \(G\), which extends Hua’s fundamental theorem of geometry on \(\mathbb{F}^{m \times n}\).
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15B33 | Matrices over special rings (quaternions, finite fields, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C45 | Eulerian and Hamiltonian graphs |
References:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer Berlin · Zbl 1134.05001 |
| [2] | Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs, Ergeb. Math. Grenzgeb. (3), vol. 18 (1989), Springer-Verlag: Springer-Verlag Berlin · Zbl 0747.05073 |
| [3] | Brouwer, A. E.; Koolen, J. H., The vertex-connectivity of a distance-regular graph, European J. Combin., 30, 668-673 (2009) · Zbl 1175.05072 |
| [4] | Chartrand, G.; Zhang, P., Chromatic Graph Theory (2009), Taylor & Francis Group: Taylor & Francis Group Boca Raton, London, New York · Zbl 1169.05001 |
| [5] | Diestel, R., Graph Theory (2000), Springer-Verlag Heidelberg: Springer-Verlag Heidelberg New York · Zbl 0945.05002 |
| [6] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer: Springer New York · Zbl 0968.05002 |
| [7] | Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0729.15001 |
| [8] | Hua, L. K., A theorem on matrices over a sfield and its applications, Acta Math. Sinica, 1, 109-163 (1951) |
| [9] | Huang, L. P., Geometry of Matrices over Ring (2006), Science Press: Science Press Beijing |
| [10] | Huang, L. P., Good distance graphs and the geometry of matrices, Linear Algebra Appl., 433, 221-232 (2010) · Zbl 1222.05159 |
| [11] | Huang, L. P., Extending Hua’s theorem on the geometry of matrices to Bezout domains, Linear Algebra Appl., 436, 2446-2473 (2012) · Zbl 1390.15104 |
| [12] | Huang, L. P.; Xiao, X., Good distance graph on rectangular matrices over a Bezout domain, (Jiang, E.-X., Proceedings of the 9th International Conference on Matrix Theory and Its Applications, vol. 2 (2010), World Academic Union (World Academic Press)), 243-246 |
| [13] | Huang, W. L.; Wan, Z. X., Adjacency preserving mappings of rectangular matrices, Beiträge Algebra Geom., 45, 2, 435-446 (2004) · Zbl 1084.15007 |
| [14] | Lidl, R.; Niederreiter, H., Finite Fields (1997), Cambridge University Press: Cambridge University Press Cambridge, (foreword by P.M. Cohn) |
| [15] | Marušič, D., Hamiltonian circuits in Cayley graphs, Discrete Math., 46, 1, 49-54 (1983) · Zbl 0515.05042 |
| [16] | Orel, M., Adjacency preservers, symmetric matrices, and cores, J. Algebraic Combin., 35, 633-647 (2011) · Zbl 1242.05167 |
| [17] | Orel, M., A note on adjacency preservers on hermitian matrices over finite fields, Finite Fields Appl., 15, 441-449 (2009) · Zbl 1183.15027 |
| [18] | Šemrl, P., On Hua’s fundamental theorem of the geometry of matrices, J. Algebra, 272, 801-837 (2004) · Zbl 1085.15019 |
| [19] | Šemrl, P., The optimal version of Hua’s fundamental theorem of geometry of rectangular matrices, Mem. Amer. Math. Soc. (2014), in press · Zbl 1301.15005 |
| [20] | Wan, Z. X., Geometry of Matrices (1996), World Scientific: World Scientific Singapore · Zbl 0866.15008 |
| [21] | Wan, Z. X., Geometry of Classical Groups over Finite Fields (2002), Science Press: Science Press Beijing, New York |
| [22] | Wan, Z. X., Lectures on Finite Fields and Galois Rings (2003), World Scientific: World Scientific New Jersey, London, Singapore, Hong Kong · Zbl 1028.11072 |
| [23] | Wan, Z. X., Design Theory (2009), Higher Education Press: Higher Education Press Beijing · Zbl 1223.05001 |
| [24] | Wang, Y. X.; Huo, Y. J.; Ma, C. L., Association Schemes of Matrices (2006), Science Press: Science Press Beijing, (in Chinese) |
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.
