Proof Let y be a solution to By=d. Then y is the linear combination of the basis that
represents d. This can be solved by Cramer's rule as Yk = det(Bk ) where Bk is the matrix
det(B)
obtained by replacing the k th column of B by d. Since B is triangular, it may be put into
lower triangular form with 1 's on the diagonal by a combination of row and column
interchanges. Therefore det(B)= + 1 or -1. Because any square submatrix of A will only
contain entries of 0 or 1 with a maximum of two 1 's in each column by the design ofthe
matrix A, every determinant of any submatrix of A will have a value of + 1, -1, or 0, so
det(Bk
)= 0, +1, or-I. Therefore Yk=O, +1, or-1.+