AbstractThe numbers of bit operations (bt) required for matrix multiplication (MM), matrix inversion (MI), the evaluation of the determinant of a matrix (Det), and the solution of a system of linear equations (SLE) are estimated from above and below. (For SLE the estimates are nearly sharp.) The bit-complexity classes turn out to be different from the arithmetical complexity classes for those problems, for instance, bt(MM) = o(bt(Det)) while MM and Det require the same number of arithmetical operations within a constant factor. The bit complexity gives a more refined measure of stability of algorithms than their condition. In particular the study shows that the large condition of the so called APA algorithms of small degrees for MM causes o...