  In this paper we study several closely related fundamental problems for words
and matrices. First, we introduce the Identity Correspondence Problem (ICP):
whether a finite set of pairs of words (over a group alphabet) can generate an
identity pair by a sequence of concatenations. We prove that ICP is undecidable
by a reduction of Post's Correspondence Problem via several new encoding
techniques.
  In the second part of the paper we use ICP to answer a long standing open
problem concerning matrix semigroups: "Is it decidable for a finitely generated
semigroup S of square integral matrices whether or not the identity matrix
belongs to S?". We show that the problem is undecidable starting from dimension
four even when the number of matrices in the generator is 48. From this fact,
we can immediately derive that the fundamental problem of whether a finite set
of matrices generates a group is also undecidable. We also answer several
question for matrices over different number fields. Apart from the application
to matrix problems, we believe that the Identity Correspondence Problem will
also be useful in identifying new areas of undecidable problems in abstract
algebra, computational questions in logic and combinatorics on words.
