Takunari Miyazaki (Trinity College, Hartford, Connecticut,)
The problem of finding a lowrank linear combination of matrices is a fundamental problem in linear algebra. In practice, the problem has also naturally arisen in cryptography (see, e.g., [Cou01a, Cou01b, FLP08,KS99]).
In this note, we consider the problem in the following decision version, which has become of some importance in computational complexity theory.
Let ${\bf F}_q$ denote a finite field of order $q > 0$.
Minimum rank ($q$) (MINRANK
($q$))
 Instance: matrices $M_0, M_1, \ldots, M_\ell \in M_{m \times n}({\bf F}_q)$ and an integer $r \le m$.
 Question: Are there $\alpha_1, \ldots, \alpha_\ell \in {\bf F}_q$ such that
Buss, Frandsen and Shallit prove in [BFS99] that, in general, MINRANK
is NPcomplete, via an elegant reduction from SAT, inspired by Valiant’s (cf. [Val79, Section 2]).
On the other hand, the wellknown Kipnis–Shamir attack on the Hidden Field Equations (HFE) protocol in [KS99] suggests that MINRANK
may admit a polynomialtime solution when the target rank $r$ is bounded by a constant. In their cryptoanalysis [FLP08], Faug`ere, LevyditVehel and Perret also propose, using a Gr"obnerbasis approach, a polynomialtime solution to MINRANK when the corank $m  r$ is bounded by a constant.
When an NPcomplete problem has a polynomialtime solution for some special cases (e.g., 2SAT), such a solution often exploits some inherent properties of the problem under the given constraints. While Faug`ere, LevyditVehel and Perret’s Gr"obnerbasis approach is impressive, it is not obvious, at least to me, exactly what properties of the problem make it solvable in polynomial time. In my view, it is thus still worthwhile to ask if there is an ``elementary’’ solution to answer the following question.
Is
MINRANK
($q$) solvable in polynomial time when the target rank $r$ or corank $m  r$ is bounded by a constant?
My interest in MINRANK originally arose while working with J. B. Wilson to investigate the complexity of testing singularity of bilinear maps (cf. [MW]).

[BFS99] J. F. Buss, G. S. Frandsen and J. O. Shallit, The computational complexity of some problems of linear algebra, J. Comput. System Sci. 58 (1999), 572–596.

[Cou01a] N. T. Courtois, La s'ecurit'e des primitives cryptographiques bas'ees sur des probl`emes alg'ebriques multivariables:
MQ
,IP
,MinRank
,HFE
, Th`ese de doctorat,Universit'e Pierre et Marie Curie (Paris VI), Paris, 2001. 
[Cou01b]    Efficient zeroknowledge authentication based on a linear algebra problem
MinRank
, Advances in Cryptology – ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Dec. 9–13, 2001, Proceedings (C. Boyd, ed.), Lecture Notes in Comput. Sci., vol. 2248, Springer, Heidelberg, 2001, pp. 402–421. 
[FLP08] J.C. Faug`ere, F. LevyditVehel and L. Perret, Cryptanalysis of
MinRank
, Advances in Cryptology – CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, Aug. 17–21, 2008, Proceedings (D. Wagner, ed.), Lecture Notes in Comput. Sci., vol. 5157, Springer, Heidelberg, 2008, pp. 280–296. 
[MW] T. Miyazaki and J. B. Wilson, Linearsize reductions and completeness in algebra, preprint.

[KS99] A. Kipnis and A. Shamir, Cryptanalysis of the HFE public key cryptosystem by relinearization, Advances in Cryptology – CRYPTO ‘99, 19th Annual International Cryptology Conference, Santa Barbara, Aug. 15–19, 1999, Proceedings (M. Wiener, ed.), Lecture Notes in Comput. Sci., vol. 1666, Springer, Heidelberg, 1999, pp. 19–30.

[Val79] L. G. Valiant, Completeness classes in algebra, Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, Apr. 30–May 2, 1979, ACM, New York, 1979, pp. 249–261.
Additional Questions?
If you have additional questions, feel free to reach out to a maintainer / contributor on the contact page.