I came up with one problem that says that a $m \times m$ matrix is invertible is the same as to say that its rows are LI (linearly independent) over $\mathbb{Z_{2}}$.

First of all, I'd like to know how to prove it, in order to prove the following:

Supposing $$z_{m+i} = \sum_{j = 0}^{m-1} c_jz_{i+j} \text{ mod 2}$$

where $(z_1, z_2, ..., z_m)$ comprises the initialization vector. For $i \geq 1$, we define:

$$v_i = (z_i, ..., z_{i+m-1})$$, observing that $v_1,... ,v_m$ are the rows of the $m \times m$ matrix.

It asks to prove with these above informations:

For any $i \geq 1$, $$v_{m+1} = \sum_{j = 0}^{m-1} c_jv_{i+j} \text{ mod 2}$$

I've calculated $v_1 = (0, c_0z_1, ..., ), v_2 = (0, c_0z_2, c_0z_2 +c_1z_3, ...)$, however I don't see a way to know how to prove that for $\alpha_i \in \mathbb{R^*}$ that:

$$\alpha_1 v_1 + \alpha_2 v_2 + \alpha_3 v_3 + ... + \alpha_m v_m = 0$$

  • 1
    $\begingroup$ This is generally given as an exercise on a linear algebra course. $\endgroup$
    – kelalaka
    Dec 22 '21 at 12:22
  • $\begingroup$ I didn't find one of such kind in my book of linear algebra. $\endgroup$ Dec 22 '21 at 12:23
  • $\begingroup$ $(\Rightarrow)$ what happens if you consider $M \times M^{-1} = Id$ modulo 2? $(\Leftarrow)$ can a zero linear combination appear when going from $\mathbb{Z}_2$ to $\mathbb{Z}$? $\endgroup$
    – Fractalice
    Dec 22 '21 at 13:23
  • 1
    $\begingroup$ Both conditions are equivalent to the kernel being null. I think the better proofs are high-level and don't rely on manipulating sums. $\endgroup$
    – bmm6o
    Dec 22 '21 at 16:42
  • $\begingroup$ I think someone then, could migrate my question to mathexchange. $\endgroup$ Dec 24 '21 at 13:24

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.