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 n^2/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 @q(n^2r). |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.ipl.2008.02.010 | Inf. Process. Lett. |
Keywords | Field | DocType |
combinatorial problems,comment math,matrix rank,z. vavrin,lower bound,lower triangular matrix,order n,short note,small gap,p. pudlak,triangular matrix,simple matrix,computational complexity,upper and lower bounds | Rank (linear algebra),Rigidity (psychology),Discrete mathematics,Combinatorics,Upper and lower bounds,Matrix (mathematics),Triangular matrix,Mathematics,Computation,Computational complexity theory | Journal |
Volume | Issue | ISSN |
107 | 5 | 0020-0190 |
Citations | PageRank | References |
1 | 0.41 | 12 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Meena Mahajan | 1 | 688 | 56.90 |
Jayalal M. N. Sarma | 2 | 46 | 5.67 |