Embedding nearly decomposable matrices into certain staircase matrices (Q915819)

A square (0,1) matrix \(D=(D_{ij})_{i,j=1,...,k}\) is called a staircase matrix if the block \(D_{ij}\) is all zeros for \(i+j\leq k\) and all ones for \(i+j\geq k+1\). An \(n\times n\) matrix is fully indecomposable if it does not contain a \(p\times (n-p)\) zero submatrix. It is nearly decomposable if it is fully indecomposable, but the matrix which results upon replacing any nonzero entry by zero is not. The problem of embedding an \(n\times n\) nearly decomposable (0,1) matrix A into a staircase matrix with L diagonals, where L is the least possible, is considered. An upper bound for L is found which depends upon A. This bound is used to find a lower bound for the minimum permanent over the face of the \(n\times n\) doubly stochastic matrices determined by A.