1
$\begingroup$

Does there exist examples of $m \times n$ matrices with $m > n$ with the property that the determinant of every $n \times n$ submatrix is at least $1$ in absolute value? (The $1$ can be replaced by $1/\text{poly}(n,m)$).

An "almost" example are totally unimodular matrices that satisfy the above property except the determinants are also allowed to be $0$. Therefore, a valid answer would be the existence of totally unimodular matrices that do not have any singular submatrices. However, I am not aware of any such constructions that do not have singular submatrices.

$\endgroup$
1
  • 2
    $\begingroup$ What about things like $\left(\begin{smallmatrix}1 & 0 \\ 0 & 1 \\ 1 & 1\end{smallmatrix}\right)$? Also, if you have any matrix whose $n \times n$-minors are nonzero, you can multiply it by a large constant to get all minors at least $1$ in absolute value... $\endgroup$ Mar 11, 2021 at 3:18

2 Answers 2

4
$\begingroup$

For any distinct integers $x_1,\ldots,x_m$ you can take the matrix whose $i$-th row $(1 \leq i \leq m)$ is $(1,x_i,x_i^2,\ldots,x_i^{n-1})$. Each $n \times n$ submatrix is Vandermonde with distinct rows, so has nonzero determinant, which being an integer must have absolute value at least $1$.

In fact the absolute value is at least $1! 2! \cdots (n-1)!$; replacing each entry $x_i^{j-1}$ by $x_i \choose j-1$ applies an invertible column transformation and retains integrality, so we still have all $n \times n$ submatrices with nonzero integral determinant, and the entries are overall smaller.

Or, if the $x_i$ are all distinct modulo some prime $p$, replace each $x_i^{j-1}$ by its remainder mod $p$ to get a matrix with all entries in $[0,p)$ and all $n \times n$ submatrices irreducible mod $p$ and thus again with determinant equal to some nonzero integer.

$\endgroup$
2
  • $\begingroup$ This is great, thanks! The prime construction works well since the entries are all 'small.' $\endgroup$ Mar 11, 2021 at 13:43
  • $\begingroup$ Follow up questions: What are the determinants of your last construction roughly? Are they roughly $p^p$? Do you think it's possible to get other constructions that have smaller determinants than the vandermonde case (which has determinant roughly $n^{n^2}$)? Thanks! $\endgroup$ Mar 11, 2021 at 14:11
1
$\begingroup$

Yes. Allow me to transpose your set-up, for reasons of my own dyslexia, and instead consider an $m \times n$ matrix $M$ with $m < n$. This matrix will have block decomposition $M = \big( D \, \big| \, A \big)$ where

$\bullet$ $D$ is the $m \times m$ anti-diagonal matrix whose $k$-th row entry is $(-1)^{k+1}$

$\bullet$ $A$ is an $m \times (n-m)$ matrix (to be specified later)

Each $m \times m$ submatrix of $M$ is uniquely prescribed by its columns, which we index by an $m$-element subset $I = \big\{i_1 < \cdots < i_m \big\} \subset \big\{ 1, \dots , n \big\}$. The determinant of the corresponding $m \times m$ submatrix will be denoted $[I]$. By design $[I]$ equals the determinant of the submatrix of $A$ whose row set $\mathrm{p}(I)$ and column set $\mathrm{q}(I)$ are

\begin{equation} \begin{array}{ll} \mathrm{p}(I) \ &= \ \big\{ m - j +1 \ \big| \ j \in \{1, \dots, m \} \, - \, I \big\} \\ \mathrm{q}(I) \ &= \ \big\{ j - m \ \big| \ j \in I \, -\, \{1, \dots, m\} \big\} \end{array} \end{equation}

It will be convenient to represent an $m$-element subset of $\{1, \dots, n \}$ by an integer partition $\lambda = \big(\lambda_1 \geq \cdots \geq \lambda_m \big)$ with at most $m$ non-zero parts and with $\lambda_1 \leq n - m$. The operative direction of this one-to-one correspondence assigns a partition $\lambda = \big( \lambda_1 \geq \cdots \geq \lambda_m \big)$ to the $m$-element subsets $I^\lambda := \big\{ 1 + \lambda_m < \cdots < m + \lambda_1 \big\}$. For brevity's sake, I shall write $[\lambda]$ in place of $[I^\lambda]$. Under this bijection, the matrix entry $A_{i,j}$ of $A$ correspond to the hook partition

\begin{equation} \langle i , j \rangle \ := \ \big(j \geq \underbrace{1 \geq \cdots \geq 1}_{\text{$i-1$ many}} \big) \end{equation}

Given any partition $\lambda$ let $s_\lambda ( \Bbb{x} )$ denote the associated Schur function in infinitely many variables $\Bbb{x} = \big(x_1, x_2, x_3, \dots \big)$. Let us now specify the matrix entries of $A$ by setting

\begin{equation} A_{i,j} \ := \ s_{\langle i, j \rangle}(\Bbb{x}) \end{equation}

then the so-called Giambelli identity asserts that

\begin{equation} s_\lambda (\Bbb{x}) \ = \ [\lambda] \end{equation}

Furthermore if we select a integer threshold $N \geq m$ and perform the specialization $x_i = 1$ whenever $1 \leq i \leq N$ and $x_i = 0$ for $i > N$ then

\begin{equation} s_\lambda \big(\underbrace{1, \dots, 1}_{\text{$N$ times}} , 0, 0, 0, \dots \big) \ = \ \dim \Bbb{S}_\lambda \big( \Bbb{C}^N \big) \end{equation}

where $\Bbb{S}_\lambda \big( \Bbb{C}^N \big)$ is the irreducible representation of $\mathrm{SL}_\mathrm{N}(\Bbb{C})$ associated to the partition $\lambda$. This value, which can be calculated using the content formula, is a positive integer for each $\lambda$ with at most $N$ non-zero parts. In particular the determinants of all maximal $m \times m$ submatrices of $M$ will be positive integers.

$\endgroup$
3
  • $\begingroup$ Thanks for this construction! I'm still trying to digest it but is it possible for you to briefly mention how large the entries of $A$ will be approximately? $\endgroup$ Mar 11, 2021 at 13:45
  • $\begingroup$ See section "Semi-standard tableaux hook length formula" of the wikipedia page on hook length formula --- en.wikipedia.org/wiki/… $\endgroup$ Mar 11, 2021 at 16:37
  • 1
    $\begingroup$ Hopefully this is correct: $A_{i,j} = {1 \over N} {i \over {i+j-1}}{N \choose i}{N+j-1 \choose j}$. $\endgroup$ Mar 11, 2021 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.