Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a vector of binary variables, $s$ representing a state at some point in time, and a transformation matrix $T$. The initial state is $s_0$.

$s_n = Ts_{n-1}$

Given a number of transformations, $n$, find the total number of times the state of each element changes. $n$ could be a very large number.

While it is quite easy to find the state after $n$ transformations in $O(lg\ {n})$ time, I am unable to find such a relation for the total number of changes.

$c_n = s_n \oplus s_{n-1} $

Need to find, $\Sigma^n_{i=1} \ c_i$.

share|improve this question
What is the dimension of s? (Number of variables) –  Shitikanth Oct 4 '12 at 5:14
$s$ is quite small (around 30) –  Vivek Oct 4 '12 at 7:08
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.