2
$\begingroup$

When discussing a transformation for cryptographic keys over on Crypto.SE I noticed that the transformation could be described using a matrix, so I wrote it up and ran some basic online-tools against it to confirm whether the function is a bijection or not and found (empirically) the following conjecture for which I'd like to ask for help in proving.

Let $\mathbb F_2^n$ be the $n$-dimensional vector space built on-top of $\mathbb F_2$, the field with the elements $0,1$ and the addition and multiplication modulo 2. Let $b\in\mathbb F_2$ (in the practical scenario the value of $b$ indicates whether we use a cyclical or a logical shift).

My conjecture is now that the following matrix is invertible iff $b=0$: \begin{pmatrix} 1&0&0&\cdots&0&b\\ 1&1&0&\cdots&0&0\\ 0&1&1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&1&1 \end{pmatrix}

Textually the matrix is the all-zero matrix with the top-right entry holding the value $b$, the diagonal being all-ones and each entry below the diagonal (if it exists) being $1$ as well.

My question is now, can this above conjecture be (easily?) proven and if so how?

I have empirically verified the above conjecture for $n=2,3,4$ but have no idea how to prove it in all generality.

$\endgroup$
  • $\begingroup$ Is it not possible for you to compute the determinant inductively? $\endgroup$ – Pedro Tamaroff Mar 1 '18 at 20:09
  • $\begingroup$ @PedroTamaroff while I see the idea, I think I completely lack the mathematical toolkit to make a proof using induction over $n$ as this would seem to bring myriads of other difficult (?) matrices when using laplace's theorem (?) to compute the new determinant in the induction step :( (And Laplace's theorem (?) is the only one I know that would remotely support something like this) $\endgroup$ – SEJPM Mar 1 '18 at 20:43
3
$\begingroup$

Following up on the determinant comment, note that by expanding through the first row, where I omit signs since you are in $\mathbb F_2$:

$$\left| \begin{matrix} 1&0&0&\cdots&0&b\\ 1&1&0&\cdots&0&0\\ 0&1&1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&1&1 \end{matrix} \right|= \left| \begin{matrix} 1&0&\cdots&0&0\\ 1&1&\cdots&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&1 \end{matrix}\right|+b \left|\begin{matrix} 1&1&0&\cdots&0\\ 0&1&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&1 \end{matrix}\right| =1+b$$ since the two matrices to the right are upper and lower triangular. This means that your matrix has $0$ determinant if and only if $b=1$, as you wanted.

$\endgroup$
  • $\begingroup$ Wow, this was way simpler than I expected. Particularly because I forgot that the $0$ will kill all but two terms in the laplace expansion. $\endgroup$ – SEJPM Mar 1 '18 at 21:08
2
$\begingroup$

When $b=1 \; \; : \; \; $Over the rational or real field, there is an eigenvalue of $2$ with eigenvector all entries equal to $1.$ However, over the field of two elements, the same eigenvector has eigenvalue $0.$

if you subtract off the identity matrix, you have a "companion matrix" for $x^n - b. $ Now that I think of it, $x^n - b$ is also the minimal polynomial for this revised matrix; whatever $b,$ we have a single Jordan block.

If you stick with the field of two elements, when $b=1$ the only eigenvalue is $1,$ so when you add $I$ back in the only eigenvalue is $0$

$\endgroup$
  • $\begingroup$ An alternative (maybe simpler) formulation would be to call the above matrix $A$ and say that the characteristic polynomial of $A-I$ is $x^n-b$ per the linked article. Now this implies $\det((A-I)-xI)=\det(A-(x+1)I)=x^n-b$ and plugging in $x=-1$ yields $\det(A)=(-1)^n-b$ which is equal to $1-b$ over $\mathbb F_2$ and which is $0$ iff $b=1$ and $\det A=0$ iff A is not invertible. [This may be easier to understand than the more fancy way using eigenvalues] $\endgroup$ – SEJPM Mar 1 '18 at 20:40
  • $\begingroup$ @SEJPM added: in field $\mathbb Z / 2 \mathbb Z$ there is an eigenvector with all entries equal to $1$ but eigenvalue $0.$ $\endgroup$ – Will Jagy Mar 1 '18 at 20:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.