# Article

Full entry | PDF   (0.3 MB)
Keywords:
real symmetric matrix; graph; multiplicity of eigenvalues; P-set; P-vertices
Summary:
Suppose that $A$ is a real symmetric matrix of order $n$. Denote by $m_A(0)$ the nullity of $A$. For a nonempty subset $\alpha$ of $\{1,2,\ldots ,n\}$, let $A(\alpha )$ be the principal submatrix of $A$ obtained from $A$ by deleting the rows and columns indexed by $\alpha$. When $m_{A(\alpha )}(0)=m_{A}(0)+|\alpha |$, we call $\alpha$ a P-set of $A$. It is known that every P-set of $A$ contains at most $\lfloor {n}/{2} \rfloor$ elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As a first step to the full characterization of these graphs of odd order, we establish some conditions for such graphs $G$ under which there is a real symmetric matrix $A$ whose graph is $G$ and contains a P-set of size ${(n-1)}/{2}$.
References:
[1] An{\dj}elić, M., Erić, A., Fonseca, C. M. da: Nonsingular acyclic matrices with full number of P-vertices. Linear Multilinear Algebra 61 (2013), 49-57; erratum ibid. 61 (2013), 1159-1160. DOI 10.1080/03081087.2013.794619 | MR 3003041 | Zbl 1315.15006
[2] An{\dj}elić, M., Fonseca, C. M. da, Mamede, R.: On the number of P-vertices of some graphs. Linear Algebra Appl. 434 (2011), 514-525. DOI 10.1016/j.laa.2010.09.017 | MR 2741238 | Zbl 1225.05078
[3] Cvetković, D., Rowlinson, P., Simić, S.: A study of eigenspaces of graphs. Linear Algebra Appl. 182 (1993), 45-66. DOI 10.1016/0024-3795(93)90491-6 | MR 1207074 | Zbl 0778.05057
[4] Du, Z.: The real symmetric matrices with a P-set of maximum size and their associated graphs. J. South China Norm. Univ., Nat. Sci. Ed. 48 (2016), 119-122. MR 3469083 | Zbl 1363.05159
[5] Du, Z., Fonseca, C. M. da: The singular acyclic matrices of even order with a P-set of maximum size. (to appear) in Filomat.
[6] Du, Z., Fonseca, C. M. da: The acyclic matrices with a P-set of maximum size. Linear Algebra Appl. 468 (2015), 27-37. MR 3293238 | Zbl 1307.15012
[7] Du, Z., Fonseca, C. M. da: The singular acyclic matrices with the second largest number of P-vertices. Linear Multilinear Algebra 63 (2015), 2103-2120. DOI 10.1080/03081087.2014.975225 | MR 3378019 | Zbl 1334.15026
[8] Du, Z., Fonseca, C. M. da: Nonsingular acyclic matrices with an extremal number of P-vertices. Linear Algebra Appl. 442 (2014), 2-19. MR 3134347 | Zbl 1282.15028
[9] Du, Z., Fonseca, C. M. da: The singular acyclic matrices with maximal number of P-vertices. Linear Algebra Appl. 438 (2013), 2274-2279. MR 3005289 | Zbl 1258.05024
[10] Erić, A., Fonseca, C. M. da: The maximum number of P-vertices of some nonsingular double star matrices. Discrete Math. 313 (2013), 2192-2194. DOI 10.1016/j.disc.2013.05.018 | MR 3084262 | Zbl 1281.05091
[11] Fernandes, R., Cruz, H. F. da: Sets of Parter vertices which are Parter sets. Linear Algebra Appl. 448 (2014), 37-54. MR 3182972 | Zbl 1286.15008
[12] Horn, R. A., Johnson, C. R.: Matrix Analysis. Cambridge University Press, Cambridge (2013). MR 2978290 | Zbl 1267.15001
[13] Johnson, C. R., Duarte, A. Leal, Saiago, C. M.: The Parter-Wiener theorem: Refinement and generalization. SIAM J. Matrix Anal. Appl. 25 (2003), 352-361. DOI 10.1137/S0895479801393320 | MR 2047422
[14] Johnson, C. R., Sutton, B. D.: Hermitian matrices, eigenvalue multiplicities, and eigenvector components. SIAM J. Matrix Anal. Appl. 26 (2004), 390-399. DOI 10.1137/S0895479802413649 | MR 2124154 | Zbl 1083.15015
[15] Kim, I.-J., Shader, B. L.: Non-singular acyclic matrices. Linear Multilinear Algebra 57 (2009), 399-407. DOI 10.1080/03081080701823286 | MR 2522851 | Zbl 1168.15021
[16] Kim, I.-J., Shader, B. L.: On Fiedler- and Parter-vertices of acyclic matrices. Linear Algebra Appl. 428 (2008), 2601-2613. DOI 10.1016/j.laa.2007.12.022 | MR 2416575 | Zbl 1145.15011
[17] Nelson, C., Shader, B.: All pairs suffice for a P-set. Linear Algebra Appl. 475 (2015), 114-118. MR 3325221 | Zbl 1312.15012
[18] Nelson, C., Shader, B.: Maximal P-sets of matrices whose graph is a tree. Linear Algebra Appl. 485 (2015), 485-502. MR 3394160 | Zbl 1322.05092
[19] Sciriha, I.: A characterization of singular graphs. Electron. J. Linear Algebra (electronic only) 16 (2007), 451-462. MR 2365899 | Zbl 1142.05344
[20] Sciriha, I.: On the construction of graphs of nullity one. Discrete Math. 181 (1998), 193-211. DOI 10.1016/S0012-365X(97)00036-8 | MR 1600771 | Zbl 0901.05069

Partner of