On the rank of random matrices over finite fields

A novel lower bound is introduced for the full rank probability of random finite field matrices, where a number of elements with known location are identically zero, and remaining elements are chosen independently of each other, uniformly over the field. The main ingredient is a result showing that...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-08
Main Authors: Salmond, Daniel, Grant, Alex, Grivell, Ian, Chan, Terence
Format: Article
Language:English
Subjects:
Fields (mathematics)
Lower bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A novel lower bound is introduced for the full rank probability of random finite field matrices, where a number of elements with known location are identically zero, and remaining elements are chosen independently of each other, uniformly over the field. The main ingredient is a result showing that constraining additional elements to be zero cannot result in a higher probability of full rank. The bound then follows by "zeroing" elements to produce a block-diagonal matrix, whose full rank probability can be computed exactly. The bound is shown to be at least as tight and can be strictly tighter than existing bounds.
ISSN:2331-8422