The full rank condition for sparse random matrices

Coja-Oghlan, Amin; Gao, Pu; Hahn-Klimroth, Max; Lee, Joon; Müller, Noela; Rolvien, Maurice

The full rank condition for sparse random matrices

Files

the-full-rank-condition-for-sparse-random-matrices.pdf (1.31 MB)

Date

2024-09-20

Authors

Abstract

We derive a sufficient condition for a sparse random matrix with given numbers of non-zero entries in the rows and columns having full row rank. The result covers both matrices over finite fields with independent non-zero entries and {0,1}-matrices over the rationals. The sufficient condition is generally necessary as well.

Keywords

Random matrix, Rank

URI

http://hdl.handle.net/2003/43969

Collections

LS 02 Komplexitätstheorie und Effiziente Algorithmen

Full item page

The full rank condition for sparse random matrices

Files

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Alternative Title(s)

Abstract

Description

Table of contents

Keywords

Subjects based on RSWK

Citation

URI

Collections