import itertools
line = ['A','B','%']
def line_permutations(line):
   if '%' not in line:
       return [line]
   line.remove('%') # use copy.copy if you don't want to modify your matrix here
   for i in range(len(line)):
       yield line[i:] + ['%'] + line[:i]
permutations = itertools.product([line_permutations(line) for line in matrix])
print(permutations)