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 square matrix $A_{n \times n}$ whose elements are either 0 or 1. The matrix $A$ changes in response to different events (the elements always being 0 or 1). After a series of changes, it finally converges to a particular matrix i.e. subsequent events do not alter $A$ significantly.

How could I determine the converged form of $A$ given that I know all the intermediate forms (say, $A_1, A_2, ..., A_n$)? Of course, if $A_n$ is the final matrix, then it would give the converged form. But, what if the convergence has already been achieved at $A_k$ where $k < n$?

I was exploring Frobenius norm a bit, and thought of using: $\lVert A_{i+1}$ - $A_i \rVert_F \leq \epsilon$. However, that does not account for any changes later in the sequence.

What would be the suggested approach in this case?

share|improve this question
    
Are the entries of each $A_i$ zero or one? In what sense do they converge? –  Alex Becker Jul 23 '12 at 21:38
    
Convergence in the sense that (most of) the individual elements of $A$ stop oscillating between 0 and 1. –  Barun Jul 23 '12 at 21:40
    
Then I'm really not sure what you're looking for. So you have an infinite sequence of matrices $A_i$ which are eventually constant, and want to know what this eventually constant value is? How are the matrices $A_i$ generated? –  Alex Becker Jul 23 '12 at 21:42
    
The sequence is actually finite. The elements represent some kind of choices, which initially fluctuate between 0 and 1, but eventually settle down to stable values. –  Barun Jul 23 '12 at 21:47
1  
Then we have to know exactly how the sequence is generated. Otherwise the best we can say is "check each $A_k$". –  Alex Becker Jul 23 '12 at 21:55

1 Answer 1

up vote 1 down vote accepted

Instead of the inequality $\|A_{i+1}-A_i\|_F\le \epsilon $ (which can indeed miss some later change in the sequence), I suggest using the condition $\max_{i\ge k}\|A_{i}-A_n\|_F\le \epsilon $ to decide whether the sequence stabilized enough. Note that the Frobenius norm for 0-1 matrices (or vectors) is just the square root of the Hamming (aka $\ell_1$) distance, and therefore is easy to compute.

Algorithmically, I would run a loop backwards: compute $\|A_{n-1}-A_n\|$, $\|A_{n-2}-A_n\|$, $\|A_{n-2}-A_n\|$,... stop when $\|A_{i}-A_n\|>\epsilon$ and declare $A_{i+1}$ as the converged state.

share|improve this answer
    
Thanks! This is a simple technique. –  Barun Jul 25 '12 at 10:35

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.