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 Ax₁ = f₁ and Ax₂ = f₂ we may assert that A(a₁x₁ + a₂x₂) = a₁f₁ + a₂f₂. Operator A was assumed to be linear after all. The expression

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. v_o and v_T were the original and the target configurations of the checkboxes. And the solution is given by v_T - v_T = sV, where V was a matrix associated with the puzzle. We know that operators associated with matrices are linear. If v_o = v_T 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. v_o and v_T 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 s₁. For other corners, the configuration must be rotated correspondingly. Denote them as s₃, s₇ and s₉ according to our enumeration rule.

2. v_o and v_T differ in the middle box of the upper row. The solution s₂ is then given by (0,1,0,1,0,1,1,0,1) or

   0	1	0
   1	0	1
   1	0	1

   Solutions s₄, s₆, and s₈ are obtained by rotation.

3. v_o and v_T differ in the middle square. s₅ = (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 v_o and v_T 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 s₁ and s₃. Which is none other than

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

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