2
$\begingroup$

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?

  • 1
    Then we have to know exactly how the sequence is generated. Otherwise the best we can say is "check each $A_k$".2012-07-23

1 Answers 1

1

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.

  • 0
    Thanks! This is a simple technique.2012-07-25