Determinants in $\mathbb{Z}_2$


Determinants in $\mathbb{Z}_2$, problem


Observe that the total number of $n\times n$ matrices with elements in $\mathbb{Z}_2$ equals $2^{n^2}.$ The number of non-zero $n\times n$ determinants over $\mathbb{Z}_2$ equals to the number of $n$ linearly independent (and ordered) rows of $n$ elements from $\mathbb{Z}_2,$ i.e., vectors in $\mathbb{Z}_2^n.$ Note also that if $a_1,\ldots,a_k,$ $k\le n,$ are linearly independent in $\mathbb{Z}_2^n,$ then there are exactly $\mathbb{Z}_2^k$ linear combinations $\displaystyle \sum_{i=1}^{k}\lambda_ia_i\in\mathbb{Z}_2^n.$ Thus there are exactly $2^n-2^k$ ways to expand the system of $k$ linearly independent vectors $a_1,\ldots,a_k,$ to a system of $k+1$ linearly independent vectors $a_1,\ldots,a_k,a_{k+1}.$

It follows that the number of non-zero determinants over $\mathbb{Z}_2$ of order $n$ is

$\displaystyle (2^n-1)(2^n-2)(2^n-2^2)\cdots (2^n-2^{n-1})=2^{n^2}\prod_{k=1}^{n}\left(1-\frac{1}{2^k}\right). $

From here $\displaystyle p_n=\prod_{k=1}^{n}\left(1-\frac{1}{2^k}\right).$ Thus, $p_n\gt p_{n+1}.$ In addition,

$\displaystyle \prod_{k=1}^{n}\left(1-\frac{1}{2^k}\right)\ge \frac{1}{2}\left(1-\sum_{k=2}^{n}\frac{1}{2^k}\right)=\frac{1}{2}\left(1-\frac{2^{k+1}-1}{2^{k+2}}\right), $


$\displaystyle \begin{align} \lim_{n\to\infty}\prod_{k=1}^{n}\left(1-\frac{1}{2^k}\right)&\ge\frac{1}{2}\lim_{n\to\infty}\left(1-\frac{2^{k+1}-1}{2^{k+2}}\right)\\ &=\frac{1}{2}\left(1-\lim_{n\to\infty}\frac{2^{k+1}-1}{2^{k+2}}\right)\\ &=\frac{1}{2}\left(1-\frac{1}{2}\right)=\frac{1}{4}. \end{align}$

Thus $\displaystyle p=\lim_{n\to\infty}p_n$ exists and $\displaystyle p\ge\frac{1}{4}.$


The problem has been offered at the 1976 Student Olympiad at the Department of Mathematics of the Moscow State University.


|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny