2

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?

Barun
  • 125
  • 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
  • So what exactly are you trying to find? – copper.hat Jul 23 '12 at 21:47
  • I wish to find the first instance $A_k$ in the sequence when the values get stabilized. – Barun Jul 23 '12 at 21:50
  • 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 Answers1

2

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.