Skip to main content
fix typos, and take care of nonhomogeneous polynomials
Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

The answer is yes.

It suffices to note that for any $n$ and $d$, there are matrices $M_1,\dots,M_n$ of the same dimension $m$ such that the set of all the products $M_{i_1}\cdots M_{i_d}$$M_{i_1}\cdots M_{i_e}$ for $1\le i_1,\dots,i_e\le n$, $1\le i_1,\dots,i_d\le n$$0\le e\le d$, is linearly independent. One possible choice is to take $m$ to be the number of nodes in the complete $d$$n$-ary tree $T$ of height $n+1$$d+1$, and $M_i$ to be the permutation matrix corresponding to the function $T\to T$ that maps each non-leaf node to its $i$-th child (and leaves anywhere).

The answer is yes.

It suffices to note that for any $n$ and $d$, there are matrices $M_1,\dots,M_n$ of the same dimension $m$ such that the set of all the products $M_{i_1}\cdots M_{i_d}$, $1\le i_1,\dots,i_d\le n$, is linearly independent. One possible choice is to take $m$ to be the number of nodes in the complete $d$-ary tree $T$ of height $n+1$, and $M_i$ to be the permutation matrix corresponding to the function $T\to T$ that maps each non-leaf node to its $i$-th child (and leaves anywhere).

The answer is yes.

It suffices to note that for any $n$ and $d$, there are matrices $M_1,\dots,M_n$ of the same dimension $m$ such that the set of all the products $M_{i_1}\cdots M_{i_e}$ for $1\le i_1,\dots,i_e\le n$, $0\le e\le d$, is linearly independent. One possible choice is to take $m$ to be the number of nodes in the complete $n$-ary tree $T$ of height $d+1$, and $M_i$ to be the permutation matrix corresponding to the function $T\to T$ that maps each non-leaf node to its $i$-th child (and leaves anywhere).

Source Link
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

The answer is yes.

It suffices to note that for any $n$ and $d$, there are matrices $M_1,\dots,M_n$ of the same dimension $m$ such that the set of all the products $M_{i_1}\cdots M_{i_d}$, $1\le i_1,\dots,i_d\le n$, is linearly independent. One possible choice is to take $m$ to be the number of nodes in the complete $d$-ary tree $T$ of height $n+1$, and $M_i$ to be the permutation matrix corresponding to the function $T\to T$ that maps each non-leaf node to its $i$-th child (and leaves anywhere).