# Superposition Principle

Superposition principle states that a linear combination of solutions to a linear equation is again a solution. In general, if V is a linear operator from one vector space to another and we have that Ax1 = f1 and Ax2 = f2 we may assert that A(a1x1 + a2x2) = a1f1 + a2f2. Operator A was assumed to be linear after all. The expression

a1x1 + a2x2

where a1 and a2 are constants, is known as a linear combination of vectors x1 and x2. (Of course, we may consider more vectors and a longer combination.) It appears that the Superposition Principle is nothing but a truism. This is to a great extent true. Which is not to say that it can't be put to a good use.

As an example, let's consider the Magic Squares puzzle. The fine theory behind the puzzle does not provide a convenient clue to its solution. Just to remind, we enumerated squares of a 3x3 board left to right top to bottom which led to a 9 dimensional boolean space. vo and vT were the original and the target configurations of the checkboxes. And the solution is given by vT - vo = sV, where V was a matrix associated with the puzzle. We know that operators associated with matrices are linear. If vo = vT there is nothing to solve. But, in a few simplest cases the two vectors differ in a single component. Let's consider three possibilities. (Note that it's actually easy to experiment with the puzzle. First solve it once. Then change one box at a time on the left board. Press the Help button to see the solution.)

1. vo and vT differ in the upper left corner. The solution is (1, 1, 1, 1, 1, 0, 1, 0, 0) or using 1 for a checked box and 0 for an unchecked one we have the following configuration:
 1 1 1 1 1 0 1 0 0

Let's call it s1. For other corners, the configuration must be rotated correspondingly. Denote them as s3, s7 and s9 according to our enumeration rule.

2. vo and vT differ in the middle box of the upper row. The solution s2 is then given by (0, 1, 0, 1, 0, 1, 1, 0, 1) or
 0 1 0 1 0 1 1 0 1

Solutions s4, s6, and s8 are obtained by rotation.

3. vo and vT differ in the middle square. s5 = (0, 1, 0, 1, 1, 1, 0, 1, 0) or
 0 1 0 1 1 1 0 1 0

Now the interesting part. Assume, for example that vo and vT differ at the two upper corners. Then the solution to the puzzle is a combination (actually a simple boolean sum or a componentwise XOR of s1 and s3. Which is none other than

 0 0 0 1 0 1 1 0 1

Thus one way to solve the puzzle is to identify the boxes where the given and target configurations differ and XOR the corresponding solutions si to partial problems.

Another fine example of application of the superposition principle comes from the study of the Stern-Brocot trees. 