The Chebyshev polynomial expansion of the one electron density matrix (DM) in electronic structure calculations is studied, extended in several ways, and benchmark demonstrations are applied to large saturated hydrocarbon systems,using a tight-binding method. We describe a flexible tree code for the sparse numerical algebra. We present an efficient method to locate the chemical potential. A reverse summation of the expansion is found to significantly improve numerical speed. We also discuss the use of Chebyshev expansions as analytical tools to estimate the range and sparsity of the DM and the overlap matrix. Using these analytical estimates, a comparison with other linear scaling algorithms and their applicability to various systems is considered. (C) 1997 American Institute of Physics. [S0021-9606(97)03947-0].