Computation of rigidity of order \(n^ 2/r\) for one simple matrix. (English) Zbl 0753.15011
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))\).
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.) |
