Calculate maximal island of ones in a matrix

Question

I have came up with a problem involving matlab and matrices with entries 1 or zero. The matrix represents people in a footballstadium, doing a wave. If a person does the wave, he has a one in the matrix, otherwise a zero. Each person has 4 neighbours, one above him, one beneath him, one to the left and one to the right. Also the persons on the boundary. For instance: $\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22}& a_{23} \\ a_{31} & a_{32} & a_{33}\end{pmatrix}$. In this matrix $a_{11}$ has neighbours $a_{13}, a_{31}, a_{12}, a_{21}$. I need to find the mass of the wave, in other words: if we have the matrix $A = \begin{pmatrix} 1&1&1&0&1\\1&1&0&0&0\\0&1&0&0&1\\1&1&0&1&0\\1&0&0&1&0 \end{pmatrix}$, i need to find out which island of ones is the biggest. We see that there are 3 islands. The first one has size 10. (The element one in the right top corner is connected to the big field of ones). The other island has size 2, the other has size 1. With programming we didn't succeed to solve this problem. But there seems to be a function in matlab that can solve this, our teacher wouldn't tell us. Can somebody give a hint?

Answer 1

Consider the 1's in the matrix $A$ as having adjacency in four directions (up/down, left/right) considered with wrap around. So in this particular example there are thirteen nodes (vertices) in an undirected graph.

The adjacency matrix is then a symmetric $13\times 13$ matrix with 1's where the row and column correspond to an adjacent pair of nodes and otherwise 0's.

Sufficiently high powers of the adjacency matrix reveal the connected components of the graph, so that the largest "island" can be found as the largest (most nodes) connected component.

Once the adjacency matrix is assembled (which depends on the contents of $A$), Matlab can compute its powers with brief commands.

Answer 2

Building on a previous answer, once you build the $M \times M$ adjacency matrix $B$ for the $M$ 1's in your original matrix (with 1's on the diagonal of $B$), you compute the $M$th power of the adjacency matrix $B^M$ and then see which column has the largest number of non-zero entries. The reason this works is that for each column $j$ in $B^M$, the non-zero entries tell you which nodes are in the connected component that contains $j$. So once you build $B$, the matlab command to get the wave size is

wave_size = max(sum(B^M > 0));