|
Prikladnaya Diskretnaya Matematika. Supplement, 2025, Issue 18, Pages 35–38 DOI: https://doi.org/10.17223/2226308X/18/7
(Mi pdma679)
|
|
|
|
Theoretical Foundations of Applied Discrete Mathematics
On the probability of incompleteness of the row rank of a random matrix consisting of independent rows with given numbers of nonzero elements
V. I. Kruglov
DOI:
https://doi.org/10.17223/2226308X/18/7
Abstract:
We consider random matrices over the rings $\mathbb{Z}_4$ or $\mathbb{Z}_8$ consisting of rows $b_1,\ldots,b_n$. Each row is chosen independently and with equal probability from all rows with weights $s_1,\ldots,s_n$ respectively. We propose upper bounds for the probability that such a random matrix has incomplete row rank. For such matrices $B$ over $\mathbb{Z}_4$ of size $n\times m$, where $n\leq m$, this probability may be bounded by the inequality \begin{gather*} \Pr[{\rm rank}(B) < n ]\leq \frac{1}{4^m}\textstyle\sum\limits_{r=1}^n \sum\limits_{1\le i_1<\ldots<i_r\le n}\sum\limits_{a_{i_1},\ldots,a_{i_r}=1}^3\sum\limits_{z_1,\ldots,z_m=\pm 1,\pm i}\prod\limits_{h=1}^r \dfrac{1}{\text{C}_m^{s_{i_h}}}\times\\\times\textstyle\sum\limits_{1\leq k_1<\ldots<k_{s_{i_h}}\leq m}L_{a_{i_h}}(z_{k_1},4)\cdot\ldots\cdot L_{a_{i_h}}(z_{k_{s_{i_h}}},4), \end{gather*} where $L_1(z,4)=L_3(z,4)=(z^3+z^2+z)/{3}$, $L_2(z,4)={3}z^2/2+{1}/{3}$. For matrices over $\mathbb{Z}_8$ we obtain a similar upper bound \allowdisplaybreaks \begin{gather*} \Pr[{\rm rank}(B) < n] \leq \frac{1}{8^m}\textstyle\sum\limits_{r=1}^n \sum\limits_{1\le i_1<\ldots<i_r\le n}\sum\limits_{a_{i_1},\ldots,a_{i_r}=1}^7\sum\limits_{z_1,\ldots,z_m=\exp(\pi li/4)\atop l=1,\ldots,8}\prod\limits_{h=1}^r \dfrac{1}{\text{C}_m^{s_{i_h}}}\times\\\times\textstyle\sum\limits_{1\leq k_1<\ldots<k_{s_{i_h}}\leq m}L_{a_{i_h}}(z_{k_1},8)\cdot\ldots\cdot L_{a_{i_h}}(z_{k_{s_{i_h}}},8), \end{gather*} where $L_1(z,8)=L_3(z,8)=L_5(z,8)=L_7(z,8)=\dfrac{z^7+\ldots+z^2+z}{7}$, $L_4(z,8)=\dfrac{4}{7}z^4+\dfrac{3}{7}$, and $L_2(z,8)=L_6(z,8)=\dfrac{2}{7}z^6+\dfrac{2}{7}z^4+\dfrac{2}{7}z^2+\dfrac{1}{7}$.
Keywords:
matrices over finite rings, random matrices, matrix rank.
Citation:
V. I. Kruglov, “On the probability of incompleteness of the row rank of a random matrix consisting of independent rows with given numbers of nonzero elements”, Prikl. Diskr. Mat. Suppl., 2025, no. 18, 35–38
Linking options:
https://www.mathnet.ru/eng/pdma679 https://www.mathnet.ru/eng/pdma/y2025/i18/p35
|
| Statistics & downloads: |
| Abstract page: | 76 | | Full-text PDF : | 25 | | References: | 16 |
|