The Cayley-Hamilton-Newton identities which generalize both the characteris
tic identity and the Newton relations have been recently obtained for the a
lgebras of the RTT-type. We extend this result to a wider class of algebras
M((R) over cap, (F) over cap) defined by a pair of compatible solutions of
the Yang-Baxter equation. This class includes the RTT algebras as well as
the reflection equation algebras.