Stochastic complements in substochastic Matrices^∗

^∗Dedicated to Professor Henryk Minc on the occasion of his retirement from the University of California, Santa Barbara.

Abstract

If

is an n × n substochastic matrix and A ₁₁ is a k × k submatrix, 1 ≤ k < n, then the stochastic complement of A ₁₁ in A is the matrix

Properties of stochastic complementation are investigated. It is shown that every stochastic complement in a substochastic matrix is a substochastic matrix, and that stochastic complementation is transitive. It is shown that every stochastic complement in an n × n substochastic matrix A n ≥ 3, is fully indecomposable if and only if A is fully indecomposable, and that every stochastic complement in a stochastic matrix B is a stochastic matrix if and only if there exist permutation matrices P and Q such that PBQ is a direct sum of fully indecomposable matrices. It is shown that every stochastic complement in a doubly stochastic matrix is doubly stochastic, that every stochastic complement in a permutation matrix is a permutation matrix, and that the permanent of each stochastic complement in a fully indecomposable doubly stochastic matrix A exceeds the permanent of A.

^∗Dedicated to Professor Henryk Minc on the occasion of his retirement from the University of California, Santa Barbara.

^∗Dedicated to Professor Henryk Minc on the occasion of his retirement from the University of California, Santa Barbara.

Notes

^∗Dedicated to Professor Henryk Minc on the occasion of his retirement from the University of California, Santa Barbara.