StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think the easiest way to see why the output vector and the number of steps are the same no matter what index you choose at each step is to look at the problem as a bunch of matrix and vector multiplications. </p> <p>For the case where <code>x</code> has 3 components, think of <code>x</code> as a 3x1 vector: <code>x = [x_0 x_1 x_2]'</code> (where <code>'</code> is the transpose operation). Each iteration of the loop will choose to flip one of <code>x_0,x_1,x_2</code>, and the operation it performs on <code>x</code> is identical to multiplication by one of the following matrices:</p> <pre><code> -1 0 0 1 1 0 1 0 1 s_0 = 1 1 0 s_1 = 0 -1 0 s_2 = 0 1 1 1 0 1 0 1 1 0 0 -1 </code></pre> <p>where multiplication by <code>s_0</code> is the operation performed if the index <code>i=0</code>, <code>s_1</code> corresponds to <code>i=1</code>, and <code>s_2</code> corresponds to <code>i=2</code>. With this view, you can interpret the algorithm as multiplying the corresponding <code>s_i</code> matrix by <code>x</code> at each iteration. So in the first example where <code>x_1</code> is flipped at the start, the algorithm computes: <code>s_1*s_2*s_0*s_1*s_2*s_1[4 -1 -2]' = [0 1 0]'</code></p> <p>The fact that the index you choose doesn't affect the final output vector arises from two interesting properties of the <code>s</code> matrices. First, <code>s_i*s_(i-1)*s_i = s_(i-1)*s_i*s(i-1)</code>, where <code>i-1</code> is computed modulo <code>n</code>, the number of matrices. This property is the only one needed to see why you get the same result in the examples with 3 elements: </p> <p><code>s_1*s_2*s_0*s_1*s_2*s_1 = s_1*s_2*s_0*(s_1*s_2*s_1) = s_1*s_2*s_0*(s_2*s_1*s_2)</code>, which corresponds to choosing <code>x_2</code> at the start, and lastly:</p> <p><code>s_1*s_2*s_0*s_2*s_1*s_2 = s_1*(s_2*s_0*s_2)*s_1*s_2 = s_1*(s_0*s_2*s_0)*s1*s2</code>, which corresponds to choosing to flip <code>x_2</code> at the start, but then choosing to flip <code>x_0</code> in the third iteration.</p> <p>The second property only applies when <code>x</code> has 4 or more elements. It is <code>s_i*s_k = s_k*s_i</code> whenever <code>k <= i-2</code> where <code>i-2</code> is again computed modulo <code>n</code>. This property is apparent when you consider the form of matrices when <code>x</code> has 4 elements:</p> <pre><code> -1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 s_0 = 1 1 0 0 s_1 = 0 -1 0 0 s_2 = 0 1 1 0 s_3 = 0 1 0 0 0 0 1 0 0 1 1 0 0 0 -1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 -1 </code></pre> <p>The second property essentially says that you can exchange the order in which non-conflicting flips occur. For example, in a 4 element vector, if you first flipped <code>x_1</code> and then flipped <code>x_3</code>, this has the same effect as first flipping <code>x_3</code> and then flipping <code>x_1</code>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload