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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.