La prima cosa che mi viene in mente è:
1) scorri la matrice e salvi ogni riga sotto forma di stringa in una lista
2) verifichi se la lista contiene stringhe ripetute

Consiglio: per la costruzione di ogni stringa usa un oggetto della classe StringBuffer in modo tale da non sprecare memoria.