# Matrix convergence — determine the converged matrix

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?

-
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
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

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.

-
Thanks! This is a simple technique. – Barun Jul 25 '12 at 10:35