The q-generalizations of the two fundamental statements of matrix algebra -- the Cayley-Hamilton theorem and the Newton relations -- to the cases of quantum matrix algebras of an "RTT-" and of a "Reflection equation" types have been obtained in [2]-[6]. We construct a family of matrix identities which we call Cayley-Hamilton-Newton identities and which underlie the characteristic identity as well as the Newton relations for the RTT- and Reflection equation algebras, in the sence that both the characteristic identity and the Newton relations are direct consequences of the Cayley-Hamilton-Newton identities.