Certain positive definite submatrices that arise from binomial coefficient matrices (Q5928462): Difference between revisions

Methods for solving an overdetermined system of compatible equations whose matrix arises from the binomial coefficients with alternating signs are discussed. The original problem is replaced by an overdetermined system of compatible equations of compatible equations (1) \(C_m\lambda= b\), where \(C_m\) is an \(n\times(n- m)\) matrix \(m\ll n\), whose nonzero elements of each column are the successive binomial coefficients with alternating signs and (1) has the same solution as the original one. It is assumed that only a subset \(A\) of the components of \(\lambda\) is nonzero. The authors study some properties of the derived matrix that are useful to the problem of choosing and solving efficiently only \(|A|\) of these equations, where \(|A|\) denotes the number of elements of \(A\) and \(|A|\leq m\). By deleting certain elements from the first and last equations one gets an equivalent system \(L_m\lambda= \widetilde b\), where \(L_m\) is an \((n-m)\times (n-m)\) Toeplitz matrix. They prove some lemmas about positive definiteness of the coefficient matrix, both for even and odd \(m\). The positive definiteness allows the choice of a positive definite subsystem of \(|A|\) equations, corresponding to a principal submatrix of \(L_m\). The symmetric case can be solved by Cholesky factorization while the nonsymmetric one by band Gauss elimination. Both these methods require \(O(m^2|A|)\) computer operations.