Source-linked AI summary
Rank-Three Projections and Minimal Multiplicity Bipartitions of Path Complements
Jintao Fei, Jiangying Luo
TL;DR
The paper determines the minimal multiplicity bipartition for complements of paths, resolving the previously open divisible-by-three orders. It constructs rank-three orthogonal projections using faithful orthogonal representations, scalable rank-one anchors, and absorption, while proving ranks one and two impossible.
Problem
The paper addresses the determination of MB for complements of paths, which requires more than knowing q(G)=2 or the minimum positive semidefinite rank.
Method
The construction uses a faithful orthogonal representation in R3, six rank-one outer-product anchors spanning S3, positive Parseval scaling, and an absorption correction for finite tails.
Results
MB(overline{P_n})=3 for n≥6, with ranks one and two excluded by a local orthogonality obstruction; the complete classification also covers the exceptional small orders.
Takeaways & Limitations
The result completely determines MB for complements of paths whenever the parameter is defined and closes the previously unresolved cases n≥9 divisible by three.
Takeaways & Limitations
The constructed projections are not established to have the SSP, and the absorption lemma provides no weight lower bound uniform in the tail size.
Abstract
from arXiv · showhide
For a graph \(G\) admitting a real symmetric realization with exactly two distinct eigenvalues, \(MB(G)\) is the minimum, over all such realizations, of the smaller of the two eigenvalue multiplicities. Adm, Fallat, Meagher, Nasserasr, Plosker, and Yang asked for this parameter for the complement of a path on at least eight vertices. We answer their question completely by proving $$ MB(\overline{P_n})=3 \qquad (n\ge 6). $$ In particular, this resolves the previously unresolved orders \(n\ge 9\) divisible by three. The proof is exact and constructive. We exhibit six vectors in \(\mathbb{R}^3\) whose mutual inner products vanish exactly for consecutive indices, whose rank-one outer products form a basis of \(\mathbb{S}^3\), and which admit a strictly positive Parseval scaling. An elementary absorption lemma then permits any finite faithful orthogonal extension of this vector chain to be added with small positive weights while the six original weights are corrected to retain the Parseval identity. The resulting Gram matrix is a rank-three orthogonal projection in \(\mathcal{S}(\overline{P_n})\). A local two-dimensional orthogonality obstruction gives the matching lower bound. For completeness, we include self-contained proofs of the exceptional small orders: \(MB(\overline{P_3})=1\), whereas \(q(\overline{P_4})=4\) and \(q(\overline{P_5})=3\).
1 Introduction
The paper frames MB(G) through two-eigenvalue realizations and orthogonal projections, then resolves the path-complement question with a uniform rank-three construction and matching lower bound.
- MB(G) is the minimum smaller eigenvalue multiplicity among two-eigenvalue realizations of G.
- MB(G) equals the least rank at most n/2 of an orthogonal projection in S(G), so q(G)=2 alone does not determine it.
- Prior work established related results for paths and rank-three realizations outside the divisible-by-three orders, leaving those residue classes unresolved.
- The resulting projection has rank three, while local orthogonality rules out ranks one and two, yielding MB(overline{P_n})=3 for n≥6.
- The construction uses a faithful orthogonal representation in R^3 plus six scalable anchor vectors whose outer products span S^3.
2 Projections, frames, and an absorption lemma
This section converts multiplicity bipartitions into Parseval-frame projections and proves an absorption lemma that preserves strict positivity when finite tails are added.
- Projection–frame equivalence: The bipartition [n−r,r] is achievable exactly when an n×r matrix U satisfies U^T U=I_r and UU^T belongs to S(G).
- Projection–frame equivalence: UU^T is then a rank-r orthogonal projection with eigenvalues 0 of multiplicity n−r and 1 of multiplicity r.
- Anchor absorption: The anchor absorption lemma starts from positive weights whose rank-one outer products span the symmetric-matrix space and sum to the identity.
- Anchor absorption: A finite tail can receive small positive weights while anchor weights receive small corrections, retaining positivity and the identity decomposition.
- Anchor absorption: Spanning is sufficient rather than linear independence, although a basis of d(d+1)/2 anchor outer products makes correction coefficients unique.
- Anchor absorption: The lemma applies to each fixed finite tail and does not provide weights uniform in tail size or imply the strong spectral property.
3 Faithful path chains in three dimensions
Faithful path chains in R^3 encode exactly the consecutive-index orthogonality pattern, and finite-avoidance arguments extend them indefinitely while preserving integrality and nonparallelism.
- Faithful path chains: A faithful path chain requires nonzero vectors whose inner product vanishes exactly when indices are consecutive.
- Faithful path chains: Its Gram matrix therefore has the path's off-diagonal zero pattern.
- Finite-avoidance extension: Finite-avoidance extension constructs the next vector while preserving the chain properties and avoiding parallelism.
- Finite-avoidance extension: The construction uses v(t)=b+tc, where b and c are nonzero orthogonal vectors derived from the preceding chain vectors.
- Finite-avoidance extension: Only finitely many parameter values create unwanted zero inner products or parallelism, so an admissible parameter exists.
- Finite-avoidance extension: Every integral faithful chain with pairwise nonparallel vectors extends to any N≥k as an integral faithful chain.
4 The six-vector anchor and the main theorem
The paper constructs a rank-three projection with the path-complement zero pattern for every n≥6, then rules out ranks one and two by a local orthogonality argument.
- The six-vector anchor: The six-vector anchor admits strictly positive weights, allowing faithful finite extensions to retain the Parseval identity.The extension is added with small positive weights while the six anchor weights are corrected.
- The six-vector anchor: Six explicit vectors provide a faithful path chain whose rank-one outer products form a basis of S3.Their inner products vanish exactly for consecutive indices, and exact calculations establish the required nonparallel and spanning properties.
- The main theorem: For every n≥6, the resulting Gram matrix is a rank-three orthogonal projection whose off-diagonal zeros occur exactly at consecutive indices.Consequently, it has the zero pattern of the path and belongs to S(Pn).
- The main theorem: Ranks one and two are impossible: in rank two, orthogonality to u2 forces u1 and u3 parallel, which then makes u1 orthogonal to u4 despite {1,4} being an edge.This contradiction establishes the matching lower bound MB(Pn)≥3.
- The main theorem: The construction is exact and effective, using integral extensions, rational correction coefficients, and rational choices of the perturbation parameter.Square roots appear only when converting positive weights into Parseval vectors.
5 Small orders and the complete classification
The small-order analysis establishes MB(P3)=1, shows q(P4)=4 and q(P5)=3, and combines these results with the main theorem for a complete classification whenever MB is defined.
- MB(P4) and MB(P5) are undefined because the parameter is defined only when q(G)=2.
- MB(P3)=1, because a rank-one projection gives q(P3)≤2 while the edge prevents q(P3)=1.
- q(P4)=4, since a permuted matrix in S(P4) is irreducible symmetric tridiagonal and therefore has simple spectrum.
- q(P5)=3, after rank-one and rank-two projection obstructions rule out q(P5)=2 and an explicit matrix proves q(P5)≤3.
- For n=1,2, the complement of the path is edgeless and has q=1; together with the main theorem, the classification covers all n≥3 where MB is defined.
6 Relation to previous constructions
The paper distinguishes faithful rank-three representations, two-eigenvalue projections, and SSP, explains how its scalable-anchor construction extends prior methods, and closes the unresolved divisible-by-three cases without proving SSP.
- A faithful orthogonal representation yields a rank-three positive semidefinite matrix, while a two-eigenvalue realization additionally requires a scalar frame operator; SSP is stricter and unnecessary for MB.
- The scalable-anchor construction places I3 inside the relative interior of a cone generated by six rank-one matrices spanning S3, enabling finite faithful path extensions to become strictly scalable.
- Prior SSP realizations covered n≥6 with 3∤n, whereas this proof applies to every congruence class and supplies the previously open cases 3∣n, n≥9.
- The paper does not establish SSP for its constructed projections, and SSP is explicitly not required for the main theorem.
7 Conclusion
For every path with at least six vertices, the complement has minimal achievable multiplicity bipartition [n−3,3], established through a rank-three realization and lower-bound obstructions.
- MB(Pn)=3 for n≥6 because a rank-three Parseval-frame realization exists while local three-consecutive-nonedge structure excludes ranks one and two.
- The proof suggests a reusable strategy: combine faithful orthogonal representations with strictly scalable rank-one anchors spanning the symmetric matrix space, then absorb remaining vertices by small positive perturbations.