A Class of Balanced Matrices Arising from Location Problems

A $( 0,1 )$-matrix is balanced if it contains no square submatrix of odd order whose row and column sums are all two. Given two collections, S = \ T₁ , ⋯ ,Tₘ \ and Q = \ T₁^ , ⋯ ,Tₙ^ \, of neighborhood subtrees of a tree T, let A( S,Q ) = ( aᵢⱼ ) be the incidence matrix with aᵢⱼ = 1 if and only if Tᵢ intersects Tⱼ^. It is shown that $A( S,Q )$ is balanced. This balancedness is then used to exhibit the existence of a polynomial algorithm to certain location problems.