r-Indecomposable and r-nearly decomposable matrices

Let n, r be integers with 0 ⩽ r ⩽ n − 1. An n × n matrix A is called r-partly decomposable if it contains a k × l zero submatrix with k + l = n − r + 1. A matrix which is not r-partly decomposable is called r-indecomposable (shortly, r-inde). Let Eij be the n × n matrix with a 1 in the (i, j) position and 0's elsewhere. If A is r-indecomposable and, for each aij ≠ 0, the matrix A − aijEij is no longer r-indecomposable, then A is called r-nearly decomposable (shortly, r-nde). In this paper, we derive numerical and enumerative results concerning r-nde matrices of 0's and 1's. We also obtain some bounds on the index of convergence of r-inde matrices, especially for the adjacency matrices of primitive Cayley digraphs and circulant matrices. Finally, we propose an open problem for further research.