XOR basis without linear algebra

XOR basis without linear algebra

By Everule, history, 4 months ago,

I think that linear algebra, is a unnecessarily intimidating tool, to solve a problem I believe is far easier, and needlessly intimidates those without formal knowledge of linear algebra, which is a significant part of codeforces. I know I didn't. Therefore I want to show a step by step problem solving process that will lead to the concept of linear basis at the end, with no formal knowledge required.

We start with the elementary problem of linear basis. Given an array , where , Choose some subset of elements in , and XOR them. Find the number of distinct elements you could make.

We start by using a simple dp. Let be the set of elements you could make with the first elements of . Then its easy to see that contains and for every . This is an algorithm, which is too inefficient.

We need to put some constraints on what looks like to make further progress. Let us assume are two elements in . Then , must also be in . This is because I can just take the elements I used to make and the elements I used to make . The elements used in both simply cancel out. This means that the new set of elements used to make is also a subset of , and therefore in .

This provides us with an equally powerful converse.

Let be some element in , and some element not in . Then , cannot be in , because if I could make and , I could make .

Another way of thinking about this is, we want to attack with some set of elements in , and kill it by getting it to .

If I could kill and , I can kill by killing first, then .

If I can kill but not , neither can I kill , because I could already get to , but I couldn't kill that either.

I recommend spending a minute internalizing this.

Now let us try adding a new element to again. I check if I can make . If I can, I can simply ignore it. If I cannot, then for is a new element too. So the size of will double. Obviously the set can double only times. This gives an algorithm in or depending on implementation.

if is large, this algorithm doesn't work either, as we cannot explicitly store . This means we will need to compress in some way. To do that, notice that there are only at most elements that matter, because the ones that I ignored, may as well not have been there. So just storing the elements , that doubled the size of , is enough. is just the set of the XORs of every subset of the compressed array.

While we successfully compressed , we lost our ability to quickly check if is in . We need to get that back.

We cannot guarantee much about the structure of . So it is hard to see an algorithm that does this quickly. However it is important to notice that its not the elements itself that are important, but more so what is the set that is generated by the compressed elements. So any edits made to the array, is okay as long it doesn't change the produced set.

We now show that the set and , produce the same . Or more generally, I can take any element, and xor it with some other element, and it will produce the same set . This is easy to prove, because if I was using in the first set, I use the first and second element in the second set. If I was using both and , then I just need the second element. It is equally good.

While this is enough to solve the given problem, it doesn't do the idea enough justice. In fact, any invertible XOR transformation from to will produce the same set.

A XOR transformation is one where is the XOR of for all in some subset of . An invertible XOR transformation, is one where there exists some XOR transformation from back to .

Let be the set of elements that are produced by and similarly define . Then because belongs to by definition, every element of also belongs to , implying . But as the operation is invertible, we can similarly argue that . This is only possible if .

Any set of the smallest size that produces is a XOR basis, and we can choose any basis of we want.

Let us now ask ourselves, what do I want my basis to look like. If some element had a "unique" bit, it would be easy to check if the element should be added to make . I just need to see if the unique bit exists in . In fact, we can do this. Let us look at the bits in decreasing order.

If no element has this bit set, we can ignore this bit. If there is already just one element with this bit set, its good already. If there are more than one, we just pick any element, and XOR it with all the other elements with this bit set to make this element the only element with this bit set.

Now since we know if this element is included, by checking the unique bit, we know when to XOR with this element. Now we need to check if the new can be made from the other elements of the basis. The other elements form a smaller basis, and we can repeat the process, and its trivial to check in a basis with only . Therefore inductively we have found an efficient, way to check if is in the basis.

I will leave optimizing this to as an exercise, as my goal was to explain the conceptual underlying forces that allow the algorithm to work.