Welcome to our community

Be a part of something great, join today!

Proving or disproving this matrix V is invertible.

kaienfr

New member
Jul 16, 2020
3
Hello everyone,
I find an interesting matrix which seems to be always invertible. But I have no idea how to prove it! So I write down here for some ideas. Here is the problem:

Let us take $n\in \mathbb{N}^*$ bins and $d\in \mathbb{N}^*$ balls. Denote the set $B = \{\alpha^1, \ldots, \alpha^m\}$ to be all possible choices for putting $d$ balls into $n$ bins (empty bin is possible), such as
$$\alpha^1 = (d,0,\ldots, 0), ~ \alpha^2 = (0,d,\ldots, 0), \ldots$$
Let us define the matrix $V$ as:
$$V = \begin{bmatrix}
(\alpha^1)^{\alpha^1} & \cdots & (\alpha^1)^{\alpha^m}\\
(\alpha^2)^{\alpha^1} & \cdots & (\alpha^2)^{\alpha^m}\\
\vdots & \vdots & \vdots\\
(\alpha^m)^{\alpha^1} & \cdots & (\alpha^m)^{\alpha^m}
\end{bmatrix}$$
where the notation $(\alpha^i)^{\alpha^j} = \displaystyle\prod_{k=1}^{n}(\alpha^i_k)^{\alpha^j_k}$, under the assumption that $0^0=1$.

Question: "is the matrix $V$ invertible?"

I have tested several examples, and it seems that $V$ is always invertible, but I have no idea how to prove it or find a counterexample.
Here are two facts I understood:
  1. all diagonal elements are strictly positives, so the trace of $V$ is strictly positive.
  2. the matrix $V$ is not symmetric.
Does anyone can help to prove or disprove the invertibility of $V$? Thanks a lot in advance for sharing any idea.
 

kaienfr

New member
Jul 16, 2020
3
For a better understanding of the problem, here is an example:

Let $n=3$ and $d=2$, then we have all possible choices for putting $2$ balls into $3$ bins as:
$$B = \{(2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1)\}.$$
The elements in the first row of the matrix $V$ are computed as:
$$(\alpha^1)^{\alpha^1} = (2,0,0)^{(2,0,0)} = 2^2\times 0^0\times 0^0 = 4,$$
$$(\alpha^1)^{\alpha^2} = (2,0,0)^{(0,2,0)} = 2^0\times 0^2\times 0^0 = 0,$$
and so on.
Thus, we have the matrix $V$:
$$V = \begin{bmatrix}
4&0&0&0&0&0\\
0&4&0&0&0&0\\
0&0&4&0&0&0\\
1&1&0&1&0&0\\
1&0&1&0&1&0\\
0&1&1&0&0&1\\
\end{bmatrix}
$$
which is clearly invertible.

Remarks: Note that, the matrix $V$ is not always triangular. as an example, for n=3, d=3, then the element $$(2,1,0)^{(1,2,0)} = 2^1\times 1^2 \times 0^0 = 2,$$ and $$(1,2,0)^{(2,1,0)} = 1^2\times 2^1 \times 0^0 = 2$$
which are both non-zeros, thus $V$ will be never invertible in this case.

Moreover, when the elements $(\alpha^i)^{\alpha^j}$ and $(\alpha^j)^{\alpha^i}$ (with $i\neq j$) are non-zeros, they may not be equal.
E.g., n=4, d=8, we have
$$(1,1,2,4)^{(2,2,2,2)} = 64$$
but
$$(2,2,2,2)^{(1,1,2,4)} = 256.$$

So, as a conclusion: "the matrix $V$ is neither triangular nor symmetric in general."