Geodesic
A probabilistic algorithm for finding the term rank of a nonnegative matrix
Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 147-156 
D. A. Kuropatkin. A probabilistic algorithm for finding the term rank of a nonnegative matrix. Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 147-156. http://geodesic.mathdoc.fr/item/DM_2005_17_1_a11/
@article{DM_2005_17_1_a11,
     author = {D. A. Kuropatkin},
     title = {A probabilistic algorithm for finding the term rank of a nonnegative matrix},
     journal = {Diskretnaya Matematika},
     pages = {147--156},
     year = {2005},
     volume = {17},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2005_17_1_a11/}
}
TY  - JOUR
AU  - D. A. Kuropatkin
TI  - A probabilistic algorithm for finding the term rank of a nonnegative matrix
JO  - Diskretnaya Matematika
PY  - 2005
SP  - 147
EP  - 156
VL  - 17
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2005_17_1_a11/
LA  - ru
ID  - DM_2005_17_1_a11
ER  - 
%0 Journal Article
%A D. A. Kuropatkin
%T A probabilistic algorithm for finding the term rank of a nonnegative matrix
%J Diskretnaya Matematika
%D 2005
%P 147-156
%V 17
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2005_17_1_a11/
%G ru
%F DM_2005_17_1_a11

Voir la notice de l'article provenant de la source Math-Net.Ru

We suggest a probabilistic algorithm for finding the term rank of a matrix with non-negative elements, find an estimate of the complexity of the algorithm, and establish an upper bound for the probability of finding a wrong value of the term rank.

[1] Sachkov V. N., Tarakanov V. E., Kombinatorika neotritsatelnykh matrits, TVP, Moskva, 2000 | MR | Zbl

[2] Mink Kh., Permanenty, Mir, Moskva, 1982 | MR

[3] Faddeev D. K., Faddeeva V. N., Vychislitelnye metody lineinoi algebry, Fizmatgiz, Moskva

[4] Solodovnikov V. I., “Verkhnie otsenki slozhnosti resheniya sistem lineinykh uravnenii”, Zapiski nauchnykh seminarov LOMI, 118 (1982), 159–187 | MR | Zbl