# Counting the number of minimal linearly dependent sets

Let's define the minimal linearly dependent subset of a matrix as below

Definition: For a matrix $$A_{m\times n}=(\boldsymbol{c}_1, \ldots, \boldsymbol{c}_n)$$ in which $$\boldsymbol{c}_i$$s are $$m$$-dimensional vectors, each set $$\mathcal{S}=\{\boldsymbol{c}_{k_1}, \ldots, \boldsymbol{c}_{k_t}\}$$ for a sequence $$k_1, \ldots, k_t\in [0:n]$$ is called a $$t$$-dimensional minimal linearly dependent subset of $$A$$, if vectors in $$\mathcal{S}$$ are linearly dependent but every $$t-1$$ members of $$\mathcal{S}$$ are linearly independent.

As an example, in the matrix \begin{align}A=\left( \begin{array}{c c c c} a&0&0&b&0&0&0\\ 0&a&0&0&b&0&0\\ 0&0&a&0&0&b&0\\ 0&0&0&a&0&0&b \end{array}\right) \end{align} we have $$\mathcal{S}_1=\{\boldsymbol{c}_1, \boldsymbol{c}_4, \boldsymbol{c}_7\}$$, $$\mathcal{S}_2=\{\boldsymbol{c}_2, \boldsymbol{c}_4\}$$, and $$\mathcal{S}_3=\{\boldsymbol{c}_3, \boldsymbol{c}_6\}$$ as $$3$$- and $$2$$-dimensional minimal subsets of $$A$$.

Upon my observation, for banded Toeplitz matrices, there should be some strong proportionality between the minimum dimension and the maximum number of total minimal linearly dependent subsets.

For example, as we see above, if we consider an $$m\times (m+3)$$ matrix formed by shifting $$(a, 0, 0, b)$$, there exists only 3 different subsets, each with dimension at least $$\frac{m+2}{3}$$. I guess there should be proportionality in the sense that, if we consider all types of banded Toeplitz, matrices, we have an increased number of higher-dimensional minimal subsets. What I like to prove is that the number is not that much, while the dimension grows.

Any idea on how can we find a tight relationship?

• Your question could use some improvement, is not very clear. For example, I don't know what you even mean by a "linear subset" of a matrix. Take a look here for tips on how to write a good question, and in particular here on how to provide some context including some basic definitions. – Lee Mosher Mar 12 at 15:19
• As I said in the comments on your other question, the term "minimal linearly dependent subset" is deceptive, or at the least not clearly understandable without some context. You have also left out the word "dependent", making it even harder to understand what you mean. – Ben Grossmann Mar 12 at 15:37
• A possible lead: Toeplitz matrices are often brought up in the context of "displacement rank"; there might be a helpful result from there. – Ben Grossmann Mar 12 at 15:44
• If you reverse the order of your columns, then you have a Hankel matrix. Maybe the Vandermonde factorization of such a matrix is useful. – Ben Grossmann Mar 12 at 15:51
• I suspect that there is "nothing special" about Toeplitz matrices, which means that generically (i.e. "in most cases"), every set of $r+1$ columns of a rank $r$ Toeplitz matrix will be a minimal linearly dependent set of columns. If the matrix has $n$ columns, that comes out to $\binom{n}{r+1}$ such sets. – Ben Grossmann Mar 12 at 15:54