# “Biggest” coefficients of a linear combination between vectors of zeros and ones

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)}$$.

References

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