A Hankel matrix is a square matrix in which each ascending skew-diagonal from left to right is constant. Let us call a matrix partial Hankel if it is the first $m Does there exist an $m$ by $n$ partial Hankel matrix $M$ such that it has $m < n/2$ rows and there is no non-zero vector $v\in\{-1,0,1\}^n$ in its kernel? Such matrices certainly do exist for non-Hankel $m$ by $n$ $\{-1,1\}$-matrices. Other that writing computer code to exhaustively explore small matrices I am not sure how to approach this question. I would be very grateful for any ideas at all.
Answer
It appears completely equivalent to ask this question for Toeplitz matrices instead of Hankel matrices. The reason is that arranging the $m$ rows of any partial Hankel matrix simply in reverse order turns it into a rectangular Toeplitz matrix but doesn't affect its kernel. I will give an answer for Toeplitz matrices below.
In another answer at MathOverflow I have argued that for "typical" $m$ by $n$ $\{0,1\}$-matrices $M$, regardless of whether they have Toeplitz (or circulant) form or not (in other words, they are chosen at random either among all $m$ by $n$ $\{0,1\}$-matrices, with uniform distribution, or within the subsets of Toeplitz or circulant matrices), the following holds:
If $w \in \{-1,0,1\}^n$ is a random vector with i.i.d. components, distributed with probabilities $P(w_i = -1) = P(w_i = 1) = \frac14$ and $P(w_i=0) = \frac12$, then the probability of $w$ lying in the kernel of $M$ is asyptotically (for large $n$) given by
$$
P(Mw=0) \sim
\begin{cases}
\quad 2^{-n} \ , \quad m > \frac{2n}{\log_2 ( \pi n/6)} \\
m^{-\frac12} \left( \frac{\pi n}6 \right)^{-\frac m2} \ , \quad m \leq \frac{2n}{\log_2 ( \pi n/6)}
\end{cases} \ .
\hspace{2cm} (1)
$$
An intermediate step of this argument effectively supports an even stronger claim, namely that for all $m$
$$
P(Mw=0) - 2^{-n} \sim m^{-\frac12} \left( \frac{\pi n}6 \right)^{-\frac m2} \ .
\hspace{2cm} (2)
$$
Since $w=0$ is always a solution of $Mw=0$ and has probability $P(w=0) = 2^{-n}$, the right hand side is essentially the asymptotic probability that $Mw=0$ with some $w \neq 0$. Consequently, since by definition every vector $w \in \{-1,0,1\}^n$ has at least probability $4^{-n}$, the probability that there exists at least one $w \neq 0$ with $Mw=0$ must then, with some suitable constant $\alpha>1$ and for large enough $n$, obey the following inequality:
$$
P(\exists w \neq 0 : Mw=0) \leq \alpha \, 4^n m^{-\frac12} \left( \frac{\pi n}6 \right)^{-\frac m2} \ .
\hspace{2cm} (3)
$$
Again, this supposes that $M$ is a random matrix, with uniform distribution over the set of all $m$ by $n$ $\{0,1\}$-matrices, or over the subset of Toeplitz matrices.
An adaptation of the above argument to $\{-1,1\}$-matrices $M$ is completely straightforward; the eigenvalues of $MM^{\rm T}$ are just scaled by a factor of $4$ (i.e. they asymptotically tend now to $n$ instead of $\frac n4$) and the single large eigenvalue $\sim \frac{mn}4$ disappears. The above inequality $(3)$ then becomes instead
$$
P(\exists w \neq 0 : Mw=0) \leq \alpha \, 4^n \left( \frac{2\pi n}3 \right)^{-\frac m2} \ .
\hspace{2cm} (4)
$$
The base 2 logarithm of the expression on the right hand side is $\log_2\alpha + 2n - \frac m2 \log_2 \left( \frac{2\pi n}3 \right)$, and so for $m > \beta \frac{4n}{\log_2 ( 2\pi n/3)}$ (with some constant $\beta>1$ of our choice) it will be bounded from above by $\alpha \, 4^{(1-\beta)n}$ and thus become arbitrarily small for large enough $n$. Recall that this is an upper bound on the probability that any randomly chosen $m$ by $n$ matrix $M$ (of the required form) will admit a nontrivial solution $w \in \{-1,0,1\}^n$ of the equation $Mw=0$. For given $n$ and $m$ there is a number $2^{n+m-1} \gg 1$ of such matrices of Toeplitz type (or $2^{nm} \gg 1$ of general form), so the probability that every single one of these will admit such a nontrivial solution must become overwhelmingly small for large $n$.
In conclusion, what the above argument tells us is that if we choose some $\beta>1$ and consider the $m$ by $n$ $\{-1,1\}$-matrices $M$, with sufficiently large $n$ and any $m$ obeying
$$
m > \beta \frac{4n}{\log_2 \left( \frac{2\pi n}3 \right)} \ ,
\hspace{2cm} (5)
$$
then with overwhelming probability there will be at least one among these matrices which has the wanted property (i.e. at least one $M$ which does not admit any nontrivial solution of $Mw=0$). This holds independently of whether we require in addition that $M$ has a Toeplitz, Hankel or circulant form. Moreover, not just one but probably the majority of all matrices of the specified form will have the wanted property.
Note that the condition $(5)$ is asymptotically weaker than $m>n/c$ for any real constant $c>1$, which implies that for any such $c$ and sufficiently large $n$ there should exist $n$ by $m$ Toeplitz (Hankel, ...) matrices with $m A final note: Of course, in the present form the entire argument is not mathematically rigorous, since it relies on several uncontrolled approximations. I believe, however, that with a little effort these holes can be filled.
No comments:
Post a Comment