Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428770 | Information Processing Letters | 2008 | 5 Pages |
Abstract
For the all-ones lower triangular matrices, the upper and lower bounds on rigidity are known to match [P. Pudlak, Z. Vavrin, Computation of rigidity of order n2/r for one simple matrix, Comment Math. Univ. Carolin. 32 (2) (1991) 213–218]. In this short note, we apply these techniques to the all-ones extended lower triangular matrices, to obtain upper and lower bounds with a small gap between the two; we show that the rigidity is .
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics