Let $n$ be a positive integer. Denote by $B_n$ the set of $n\times(n+1)$-matrices of rank $n$ and with coefficients in $\{0,1\}$. I would like to measure how "complex" the coefficients of a linear combination of the columns of a matrix of $B_n$ can be. More precisely, I'd like to compute (or estimate the asymptotic behaviour of) $$ P_n := \max \left\{ \prod_{i=1}^{n+1}|\lambda_i|,\; M\in B_n,\; \sum_{i=1}^{n+1}\lambda_i m_{\star,i} = 0,\; \lambda_1,\dots,\lambda_{n+1}\in \mathbb{Z},\; \gcd(\lambda_1,\dots,\lambda_{n+1})=1 \right\} $$

where $m_{\star,i}$ stands for the $i$-th column vector of the matrix $M$.

$P_2=1$ and $P_3 = 2$, and for every $1\le k\le n-2$ with $\gcd(k,n-1)=1$, $P_n$ is bounded below by $(n-1)(n-(k+1))^{k}k^{n-k}$ (indeed, setting $v$ the vector whose $k$ first coefficients are 1 and $n-k$ last coefficients are 0 and $\hat e_i$ the vector whose only 0 coefficient is at line i and whose other coefficients are 1, we have the following combination: $ (n-1) v + (n-(k+1))(\hat e_1 +\dots + \hat e_k) = k(\hat e_{k+1} +\dots + \hat e_n).) $


We can show that $P_n\le (n+1)^{n(n+1)}$ for each $n\ge 2$, becuase a few months ago I proved a following lemma.

For a natural number $n$ let $[n]$ denotes a set ${1,\dots, n}$. Given a subset $Y$ of a vector space $X$ over $\mathbb R$ by $\langle Y\rangle$ we denote the linear hull of $Y$ in $X$, that is a set of all finite sums $f_1y_1+\dots+f_ky_k$, where $f_i\in\mathbb R$ and $y_i\in Y$ for each $i$.

Lemma. Let $K$ and $N$ be positive integers, $V=\{v_1,\dots, v_k\}\subset [0,K]^N$ be a linearly dependent over $\mathbb R$ system of vectors with integer entries. There exist integers $f_1,\dots, f_k$ which are not all zeroes such that $|f_i|\le (kK)^{k-1}$ for each $i$ and $f_1v_1+\dots+f_kv_k=0$.

Proof. Let $W$ be a maximal linearly independent subset of a set $V$. Since the set $V$ is linearly dependent, $|W|\le k-1$. For each $i\in [N]$ let $e^i=(e^i_1,\dots,e^i_N)\in\mathbb R^N$ be $i$-th standard orth, that is $e^i_i=1$ and $e^i_j=0$ for each $j\ne i$. Let $B_0=\{e^1,\dots,e^n\}$ be the standard basis of the linear space $\mathbb R^N$. By [Lan, Ch. III, Theorem 2], there exists a basis $B$ of the space $\mathbb R^N$ such that $W\subset B\subset W\cup B_0$. Let $C=B_0\setminus (B\setminus W)$ and $p_{C}:\mathbb R^N\to \langle C\rangle$ be the orthogonal projection, that is $p_{C}(x)=\sum\{x_ie^i:x_i\in\mathbb R$, $e^i\in C\}$ for each vector $x=(x_1,\dots,x_N)\in \mathbb R^N$. Thus $\ker p_{C}=\{x\in \mathbb R^N:p_{C}(x)=0\}=\langle B_0\setminus C\rangle= \langle B\setminus W\rangle$. We have $\ker p_{C}\cap \langle W\rangle=\langle B\setminus W\rangle\cap\langle W\rangle=0$, because otherwise the set $B$ is linearly dependent. Thus the restriction $p_{C}|\langle W\rangle$ of the map $p_{C}$ on the set $\langle W\rangle$ is injective.

Put $K'=(kK)^{k-1}$. Define a map $f$ from the subset $D^k$ of points of the set $[0, K']^k$ with all integer coordinates to $\langle W\rangle\cap \mathbb Z^N\subset \mathbb R^N$ as follows. Let $d=(d_1,\dots,d_k)\in D^k$. Put $f(d)=p_C(dv)$, where $dv=d_1v_1+\dots d_kv_k$. Since $d_i\in [0, K']$ and $v_i\in [0,K]^N$ for each $i\in [k]$, each coordinate of a vector $dv$ (and, hence, of the vector $f(d)=p_C(dv)$ too) is at most $kK'K$. Since $$|C|=|B_0\setminus (B\setminus W)|=|B_0|-|B\setminus W|=|B_0|-(|B|-|W|)= N-(N-|W|)=|W|\le k-1,$$ $|f(Q)|\le (kK'K+1)^{k-1}$. We have $|D^k|>|f(Q)|$, because $(1+(kK)^{k-1})^{\frac 1{k-1}}>(1+(kK)^k)^{\frac 1{k}}$, because when $a>1$ is a constant and $x>0$ a function $(1+a^x)^{\frac 1x}$ decreases. Therefore the function $f$ is not injective. So there exist distinct elements $d=(d_1,\dots,d_k)$ and $d'=(d'_1,\dots,d'_k)$ of $D^k$ such that $p_C(dv)=f(d)=f(d')=p_C(d'v)$. Since $dv$ and $dv'$ belong to $\langle W\rangle$ and the restriction $p_{C}|\langle W\rangle$ is injective, $dv=d'v$. It remains to put $f_i=d_i-d'_i$ for each $i\in [k]$.$\square$

Remark that for each $B_n$, the sequence $(\lambda_1,\dots,\lambda_{n+1})$ is determined up to a multiplication by $(-1)$. The lemma implies that $|\lambda_i|\le (n+1)^n$ for each $i$, so $P_n\le (n+1)^{n(n+1)}$.


[L] Serge Lange, Algebra, Addison-Wesley, 1965 (Russian translation, Moskow, Mir, 1968).


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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