We build a combinatorial technique to solve several long standing problems in linear algebra with a particular focus on algorithmic complexity of matrix completion and tensor decomposition problems. For all appropriate integral domains R, we show the polynomial time equivalence of the problem of the solvability of a system of polynomial equations over R to • the minimum rank matrix completion problem (in particular, we answer a question asked by Buss, Frandsen, Shallit in 1999), • the determination of matrix rigidity (we answer a question posed by Mahajan, Sarma in 2010 by showing the undecidability over Z, and we solve recent problems of Ramya corresponding to Q and R), • the computation of tensor rank (we answer a question asked by Gonzalez, Ja'Ja' in 1980 on the undecidability over Z, and, additionally, the special case with R = Q solves a problem posed by Blaser in 2014), • the computation of the symmetric rank of a symmetric tensor, whose algorithimic complexity remained open despite an extensive discussion in several foundational papers. In particular, we prove the NP-hardness conjecture proposed by Hillar, Lim in 2013. In addition, we solve two problems on fractional minimal ranks of incomplete matrices recently raised by Grossmann, Woerdeman, and we answer, in a strong form, a recent question of Babai, Kivva on the dependence of the solution to the matrix rigidity problem on the choice of the target field.