Computation of rigidity of order \(n^ 2/r\) for one simple matrix. (English) Zbl 0753.15011

Pudlák, Pavel; Vavřín, Zdeněk

Commentat. Math. Univ. Carol. 32, No. 2, 213-218 (1991).

The authors examines the following interesting problem: Let \(M\) be a square matrix of type \(n\) over an arbitrary field \(F\). Which is the minimal number of changes in \(M\) needed no reduce its rank to a value less or equal to \(r?\)
This so-called rigidity problem was introduced in connection with lower bounds to the size of circuits. The above mentioned minimal number (the rigidity of \(M\)) is defined by the equality: \(R^ F_ M(r)=\min\{| B|, M=A+B,\;r(A)\leq r\}\) where \(| B|\) denotes the number of nonzero elements in \(B\) and \(r(A)\) denotes the rank of \(A\).
The authors compute the exact value of rigidity of the triangular matrix \(T_ n\) with entries 0 and 1 and determine the optimal decompositions of rank \(r\) of this matrix. (A decomposition \(T_ n=A+B\) is optimal iff \(| B|=R^ F_ M(r))\).

Reviewer: Á.G.Horváth (Budapest)

MSC:

15B36	Matrices of integers
15A03	Vector spaces, linear dependence, rank, lineability
05B20	Combinatorial aspects of matrices (incidence, Hadamard, etc.)
68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)

Keywords:

rigidity of matrices; lower bounds to complexity; size of circuits; triangular matrix; optimal decompositions