is that,as Ivan Sanov proved in 1947,any sequence of multiplications of these matrices is not identity unless one can keep applying AA=BB1=I2 to cancel all the multiplications. Now with this,the algorithm becomes easy.Just keep multiplying the matrices and check whether finally the matrix is I2.For example,if I see abbabba'bba,thenIjust multiply ABBAB-BABBA,and at any time I only need to keep a 2x2 matrix There is one catch here:as we see from the above examples,some entries may become larger and larger as the multiplication goes on.But this turns out not to be a problem.Let's see a randomized algorithm here,and the deterministic algorithm follows from the same idea,though a few more (elementary)number theory results are needed.Pick a random prime p,and do all the computation mod p.If a matrix M is not I,then at least one entry in M-I is not 0.Then for a random prime p,the probability that the entry mod p becomes zero is very small. Remark: You've seen the essential idea ofthe algorithm.In case that you really want to make sure all details work out,here it is.Each entry can be at most exponentially large,so it only has a polynomial number of prime factors.Thus picking a random prime from a larger polynomial range avoids these prime factors with high probability.For more details of this as well as the deterministic algorithm,see the original paper [LZ77]. You don't need to know any group theory to understand the above.But in case that you are fairly familiar with language of groups and their representations,then Sanov's theorem says that the mapping“a→A and b→B”is a faithful representation of the free group on a and b. 1.2 Barrington's theorem Recall that the parity function Parity(x)is defined as I if the number of I's in x is odd,and 0 otherwise.Do you think computing Parity(x)needs a lot ofspace? After considering the above question,let's change the function to Majority(x).Do you think it needs more space than Parity? In general,let's consider a computation model called branching programs.A(deterministic) branching program for a given Boolean function f ofn variables x1,...,xn is a directed acyclic graph (DAG).Parallel edges are allowed.There is one particular node called source;there are also two other nodes called sinks,labeled by 1 (accept)and by 0(reject).Each non-sink node is labeled by a variable xi,and the node has exactly 2 outgoing edges,labeled by xi=0 and x;=1.is that, as Ivan Sanov proved in 1947, any sequence of multiplications of these matrices is not identity unless one can keep applying AA-1 = BB-1 = I2 to cancel all the multiplications. Now with this, the algorithm becomes easy. Just keep multiplying the matrices and check whether finally the matrix is I2. For example, if I see abbab-1ba-1b -1b -1 a, then I just multiply ABBAB-1BA-1B-1B-1A, and at any time I only need to keep a 22 matrix. There is one catch here: as we see from the above examples, some entries may become larger and larger as the multiplication goes on. But this turns out not to be a problem. Let’s see a randomized algorithm here, and the deterministic algorithm follows from the same idea, though a few more (elementary) number theory results are needed. Pick a random prime p, and do all the computation mod p. If a matrix M is not I, then at least one entry in M-I is not 0. Then for a random prime p, the probability that the entry mod p becomes zero is very small. Remark:  You’ve seen the essential idea of the algorithm. In case that you really want to make sure all details work out, here it is. Each entry can be at most exponentially large, so it only has a polynomial number of prime factors. Thus picking a random prime from a larger polynomial range avoids these prime factors with high probability. For more details of this as well as the deterministic algorithm, see the original paper [LZ77].  You don’t need to know any group theory to understand the above. But in case that you are fairly familiar with language of groups and their representations, then Sanov’s theorem says that the mapping “a→A and b→B” is a faithful representation of the free group on a and b. 1.2 Barrington’s theorem Recall that the parity function Parity(x) is defined as 1 if the number of 1’s in x is odd, and 0 otherwise. Do you think computing Parity(x) needs a lot of space? After considering the above question, let’s change the function to Majority(x). Do you think it needs more space than Parity? In general, let’s consider a computation model called branching programs. A (deterministic) branching program for a given Boolean function f of n variables x1, …, xn is a directed acyclic graph (DAG). Parallel edges are allowed. There is one particular node called source; there are also two other nodes called sinks, labeled by 1 (accept) and by 0 (reject). Each non-sink node is labeled by a variable xi , and the node has exactly 2 outgoing edges, labeled by xi = 0 and xi= 1