Gaussian Elimination with Partial Pivoting over Finite Fields (GEPPFF)
Category: Local Optimality
Input
An $n \times n$ matrix $A$ with entries over a finite field and an integer $l$.
Problem
What is the smallest row index in the $l^\text{th}$ column that is nonzero when Gaussian elimination with partial pivoting is performed on $A$?
Status
Open (Greenlaw, Hoover and Ruzzo [2]).
Remarks
Vavasis shows the analogous problem for unrestricted fields is $\P$-complete [1], see GEPP.