Say one is given a Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) of dimension $2^q \times k$ such that the elements of the first column of it are $\{0,1,2,..,-1+2^q\}$. (This then uniquely specifies the matrix). Now say one enlarges this to a matrix of dimension $2^q \times (1+q(k-1))$ over $\{0,1\}$ by replacing all the entries (except the first column) by its bit-string in binary representation.

Are there known relationships between the two matrices? Any easy way to relate them?
Like I believe it remains true that every subset of $k$ rows of the new matrix are also linearly independent (over $\mathbb{F}_2$?). How does one see this?

EDIT : In the original matrix itself assume that all arithmetic are being done "mod $2^q$" so that all entries in the Vandermonde matrix are elements of $\mathbb{F}_{2^q}$ and hence everyone has a $q-$bit representation.

  • $\begingroup$ Is it the full binary representation where the original last column already takes up $q(k-1)$ binary columns, or we truncate all the binary representations by modulo $2^q$? In the second case your assertion is not true. $\endgroup$ – Willard Zhan Oct 9 '17 at 20:03
  • $\begingroup$ @WillardZhan Please see the updated EDIT. I have clarified this. Thanks1 $\endgroup$ – gradstudent Oct 10 '17 at 1:30
  • $\begingroup$ Are you working on erasure coding? $\endgroup$ – Deep Joshi Oct 10 '17 at 3:05
  • $\begingroup$ I wasnt thinking of such a connecṭion. But if you have seen this somewhere then please share the reference! $\endgroup$ – gradstudent Oct 10 '17 at 3:18
  • $\begingroup$ @gradstudent The arithmetic in $\mathbb{F}_{2^q}$ and in $\mathbb{Z}/2^q\mathbb{Z}$ are different. If it is the later one which is modulo $2^q$, then a counterexample is $q=3,k=4$ and the rows corresponding to $0,2,4,6$ are linearly dependent. $\endgroup$ – Willard Zhan Oct 10 '17 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.