On the Maximum Probability of Full Rank of Random Matrices over Finite Fields
The problem of determining the conditions under which a random rectangular matrix is of full rank is a fundamental question in random matrix theory, with significant implications for coding theory, cryptography, and combinatorics. In this paper, we study the probability of full rank for a <inline...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-02-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/3/540 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The problem of determining the conditions under which a random rectangular matrix is of full rank is a fundamental question in random matrix theory, with significant implications for coding theory, cryptography, and combinatorics. In this paper, we study the probability of full rank for a <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>K</mi><mo>×</mo><mi>N</mi></mrow></semantics></math></inline-formula> random matrix over the finite field <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi mathvariant="double-struck">F</mi><mi>q</mi></msub></semantics></math></inline-formula>, where <i>q</i> is a prime power, under the assumption that the rows of the matrix are sampled independently from a probability distribution <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">P</mi></semantics></math></inline-formula> over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msubsup><mi mathvariant="double-struck">F</mi><mi>q</mi><mi>N</mi></msubsup></semantics></math></inline-formula>. We demonstrate that the probability of full rank attains a local maximum when the distribution <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">P</mi></semantics></math></inline-formula> is uniform over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi mathvariant="double-struck">F</mi><mi>q</mi><mi>N</mi></msubsup><mo>∖</mo><mrow><mo>{</mo><mn>0</mn><mo>}</mo></mrow></mrow></semantics></math></inline-formula>, for any <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>K</mi><mo>⩽</mo><mi>N</mi></mrow></semantics></math></inline-formula> and prime power <i>q</i>. Moreover, we establish that this local maximum is also a global maximum in the special case where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>K</mi><mo>=</mo><mn>2</mn></mrow></semantics></math></inline-formula>. These results highlight the optimality of the uniform distribution in maximizing full rank and represent a significant step toward solving the broader problem of maximizing the probability of full rank for random matrices over finite fields. |
|---|---|
| ISSN: | 2227-7390 |