Exponent Profiles of Oscillatory Matrices under Matrix and Inverse Sparsity

Abstract

We classify the simultaneous half-bandwidths $p,q$ of a symmetric oscillatory matrix $A$ and its inverse. At order $n\ge 2$, the possible pairs are $(1,n-1)$, $(n-1,1)$, and all pairs with $2\le p,q\le n-1$. Let $e_k(A)$ be the least positive integer $m$ for which all minors of order $k$ of $A^m$ are positive, and let $e(A)={\max }_{1\le k<n}{e}_k(A)$. Put $a=\min \{p,q\}$ and $b=\max \{p,q\}$. At every feasible pair of actual half-bandwidths, \[ \max_A e(A)= \max\left\{\left\lfloor\frac n2\right\rfloor, n-a-\left\lfloor\frac{\max\{n-p-q,0\}}{b}\right\rfloor\right\}. \] We also determine the maximum of ${\sum }_{k=1}^{n-1}{e}_k(A)$ for every pair. When $p+q\ge n$, one realization maximizes all $e_k$ simultaneously. Write $A=U^T\Delta U$, with $U$ unit upper triangular and totally nonnegative, and $\Delta$ positive diagonal. Let $\ell (U)$ be the least number of elementary upper bidiagonal factors with positive parameters whose product is $U$. At fixed $(p,q)$, its minimum is $\max \{n-1,p+q-1\}$. One symmetric integer matrix of determinant one simultaneously attains this minimum, the maximum exponent, and the maximum exponent sum. We prove $\ell (U^{r+1})-\ell (U^r)=\#\{k:1\le k<n,e_k(A)>r\}$ for every integer $r\ge \lfloor (n-1)/2\rfloor$, with the starting point optimal. With $\delta =\ell (U)-n+1$, the exponent sum satisfies $\delta \le n(n-1)/2-{\sum }_{k=1}^{n-1}{e}_k(A)\le \lfloor (n-1)/2\rfloor \delta$, with both constants sharp. The lower deficit bound is attained at every admissible factor count. Within the symmetric class, a total sum of $n(n-1)/2$ characterizes basic matrices. In the basic oscillatory class, without a symmetry assumption, a positive integer vector $(f_1,\dots ,f_{n-1})$ is realizable if and only if $f_k\le \max \{k,n-k\}$ and $f_k+f_{n-k}\ge n$ for $1\le k<n$, and $|f_{k+1}-f_k|\le 1$ for $1\le k<n-1$. Explicit factor orders realize every such vector.

arXiv comment32 pages, 0 figures. Added the exact maximum exponent in the sparse bandwidth range and a sharp cutoff for factor-count increments