Patterns that Require Distinct Singular Values Journal: Linear Algebra and Its Applications

Caleb Cheung, Bryan Shader · 2025

Read Patterns that Require Distinct Singular Values Journal: Linear Algebra and Its Applications by Caleb Cheung, Bryan Shader (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-12641.txt.

Introduction

Caleb Cheung and Bryan Shader study patterns of zeros and nonzeros in rectangular matrices. Their question is which patterns force every real matrix with that pattern to have all distinct singular values, meaning no two of them repeat. They work with patterns whose term rank equals the number of rows, and they give a full characterization of the patterns with this property.

The result extends an older theorem by Fiedler about symmetric matrices and repeated eigenvalues. Fiedler had shown that paths are the only graphs for which every symmetric matrix with that graph avoids repeated eigenvalues. Cheung and Shader prove the matching statement for singular values in the rectangular case. The paper is a compact piece of matrix theory that pins down exactly when a pattern rules out repetition.

Catalog record

CREATORCaleb Cheung, Bryan Shader
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-12641

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Patterns that Require Distinct Singular Values Journal: Linear Algebra and Its Applications Caleb Cheung, Bryan Shader Abstract 1 Introduction Identifying the properties of a structured matrix (e.g., with a given zero-nonzero pattern, or a given are sign-pattern) that allow a multiple eigenvalue is of interest in mechanical engineering (where the presence of a multiple eigenvalue of the stiffness matrix allow for more complex vibration patterns), and in functional biology (where the presence of a multiple eigenvalue corresponds to multiple equilibria and the ability for a cell to specialize). See [ 8 ] and references therein for more details. Perhaps the first result along these lines is that of Fiedler [ 5 ] , which shows that the graphs that forbid a multiple eigenvalue are the paths (see below for more specific details). In this paper, we study the analogous problem for singular values. In particular, we determine the zero-nonzero patterns that forbid a multiple singular value (under a minor natural assumption on the patterns). Throughout the paper, all matrices are over the reals. The singular values of the m\times n matrix A are the nonnegative square roots of the eigenvalues of AA^{\top} . We denote the multi-set of the singular values of A by \Sigma(A)=\{\sigma_{1},\dots,\sigma_{m}\} , and, as is standard, assume \sigma_{1}\geq\sigma_{2}\geq\dots\geq\sigma_{m} . We use O to denote a zero matrix and I to denote the identity matrix of the appropriate size. All vectors are boldfaced, and \mathbf{0} denotes the zero vector. The direct sum of the m\times n matrix A and the k\times\ell matrix B is denoted by A\oplus B and is the (m+k)\times(n+\ell) block diagonal matrix \displaystyle A\oplus B=\begin{bmatrix}\begin{array}[]{r|r}A&O\\ \hline\cr O&B\end{array}\end{bmatrix}. A pattern is a matrix P=[p_{ij}] each of whose entries belongs to \{0,1\} . A superpattern of P is a pattern obtained by changing some zeros of P to ones. The pattern of the matrix A is the matrix obtained from A by replacing each nonzero entry with a 1 . The set of all matrices with pattern P is denoted by \mathcal{Z}(P) . The term-rank of the m\times n matrix A is the largest number of nonzero entries of A with no two in the same row and column. We say A has full term-rank if its term-rank is \min\{m,n\} . In [ 6 ] , Fiedler showed that paths are precisely the graphs G for which every symmetric matrix whose graph is G has only simple eigenvalues. In this paper, we study the analogous problem for singular values. In particular, we characterize the m\times n patterns P with m\leq n and term-rank m for which every matrix with pattern P has only simple singular values. Unfortunately, allowing a matrix with a certain list of singular values is not inherited by superpatterns. There is a property, which we make use of, that guaranties inheritance. The matrix A has the Strong Singular Value Property (SSVP) if O is the only matrix X such that (a) A^{\top}X is symmetric, (b) XA^{\top} is symmetric, and (c) A\circ X=O . Here \circ denotes the entrywise product of matrices. Implications of the SSVP are developed in [ 3 ] . In particular, Theorem 3.10 of that paper shows that every matrix with the SSVP has full term-rank; and Theorem 4.1 asserts that if A has pattern P and the SSVP, then for each superpattern \widehat{P} of P there exists a B matrix in \mathcal{Z}(\widehat{P}) such that \Sigma(B)=\Sigma(A) . We note that there are related, but fundamentally different investigations in the recent literature, e.g., the Strong Inner Product Property [ 4 ] , which studies the relationship between patterns and row orthogonality, and the Asymmetric Strong Arnold Property [ 1 ] which concerns the combinatorial structure of rectangular matrices and their rank. The remainder of the paper is structured as follows. In Section 2, we construct families of square patterns that allow a matrix with multiple singular values and the SSVP. Using this list, we classify the square patterns with full term-rank that require all singular values to be simple. In Section 3, we extend the characterization to rectangular matrices of full term-rank. In Section 4, we discuss square patterns that allow multiple singular values with less than full term-rank. 2 Square Patterns Requiring Simple Singular Values Inverse singular values problems for patterns (ISVP-P) were introduced and studied in [ 3 ] . Here we recall needed results from that paper. First, it is shown that for each matrix A with the SSVP, and each superpattern of that of A there exists a matrix with the chosen superpattern and the same singular values as A . The formal statement is as follows (Theorem 4.1 of [ 3 ] ). Theorem 2.1 ( Superpattern Theorem). Let A have the SSVP and P be a superpattern of the pattern of A . Then there exists a matrix with pattern P and singular values \Sigma(A) . Such flexibility is dependent on A having the SSVP. A weaker result, the Matrix Liberation theorem, allows one to perturb a matrix A without the SSVP in certain directions to a matrix B with \Sigma(B)=\Sigma(A) . To understand the statement of the theorem, we introduce some definitions. We view the set \mathbb{R}^{m\times n} of all m\times n real matrices as an inner-product space with inner-product \langle A,B\rangle=\mbox{tr}(A^{\top}B) , where ⊤ and tr indicate the transpose and trace of a matrix, respectively. Let A be an m\times n matrix, and S be an m\times n superpattern of the pattern of A . The matrix A has the SSVP with respect to S provided Y=O is the only m\times n matrix such that (a) A^{\top}Y is symmetric, (b) YA^{\top} is symmetric, and (c) S\circ Y=O . The tangent space of A , denoted \mbox{Tan}^{\Sigma}_{A} , is the collection of matrices of the form KA+AL where K is an m\times m , respectively L is an n\times n , skew-symmetric matrix. The normal space of A , denoted \mbox{Norm}^{\Sigma}_{A} is the orthogonal complement of the tangent space of A . In [ 3 ] it is shown that \mbox{Norm}^{\Sigma}_{A} is the set of all matrices X such that both A^{\top}X and XA^{\top} are symmetric. For an m\times n pattern P=[p_{ij}] , and an m\times n matrix D=[d_{ij}] , the pattern of P in the direction D is the m\times n pattern S=[s_{ij}] with s_{ij}=1 if and only if p_{ij}=1 or d_{ij}\neq 0 . The following is Theorem 4.5 of [ 3 ] Theorem 2.2 ( Matrix Liberation Theorem). Let A be an m\times n matrix with pattern P , D be a matrix in \mbox{\rm Tan}^{\Sigma}_{A} and S be the pattern of P in the direction of D . If A has the SSVP with respect to S , then there is a matrix B with pattern S having the SSVP, the same singular values as A and pattern S . Another tool we need is the Direct Sum theorem, which classifies the matrix direct sums having the SSVP (Theorem 3.12 of [ 3 ] ). Theorem 2.3 ( Direct Sum Theorem). Let A be an m\times n matrix, B be a p\times q matrix and M=A\oplus B with m+p\leq n+q . Then M has the SSVP if and only if each

Read the complete text