number of subrectangles

Question

I have a square matrix generated by a cyclic shift of a vector which contains only 0's and 1's. For example, $$ \begin{matrix} 1 \; 1 \; 0 \; 1 \; 1 \\ 1 \; 1 \; 1 \; 0 \; 1 \\ 1 \; 1 \; 1 \; 1 \; 0 \\ 0 \; 1 \; 1 \; 1 \; 1 \\ 1 \; 0 \; 1 \; 1 \; 1 \end{matrix} $$ I would like to count the number of rectangles which have 1's as their vertices and which edges are parallel to rows and columns of the matrix. Here are the examples of such rectangles (the vertices are bold): $$ \begin{matrix} \textbf{1} \; \textbf{1} \; 0 \; 1 \; 1 \\ \textbf{1} \; \textbf{1} \; 1 \; 0 \; 1 \\ 1 \; 1 \; 1 \; 1 \; 0 \\ 0 \; 1 \; 1 \; 1 \; 1 \\ 1 \; 0 \; 1 \; 1 \; 1 \end{matrix} \; \; \; \; \; \begin{matrix} \textbf{1} \; 1 \; 0 \; 1 \; \textbf{1} \\ 1 \; 1 \; 1 \; 0 \; 1 \\ 1 \; 1 \; 1 \; 1 \; 0 \\ 0 \; 1 \; 1 \; 1 \; 1 \\ \textbf{1} \; 0 \; 1 \; 1 \; \textbf{1} \end{matrix} $$ I believe, there is an algorithm which solves this problem, but since the structure of the matrix is known it seems to me there must be an analytic approach. Is it possible to compute this number in general case for arbitrary generating vector?

Answer 1

For each $i\in \{0,1,\dots,n-1\}$, let $b_i$ be the zero-one vector describing the $i^\text{th}$ row. The number of rectangles between $b_i$ and $b_j$ is $\binom{b_i\cdot b_j}2$, where $b_i\cdot b_j$ is the dot product between rows numbered $i$ and $j$. This is because there are $b_i\cdot b_j$ columns where there is a one in both rows $i$ and $j$, and a rectangle is given by choosing two such columns.

You can then get the total number of rectangles by summing that quantity over all $0\le i<j\le n-1$. $$ \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1} \binom{b_i\cdot b_j}{2}=\frac12\sum_{i=0}^{n-1}\sum_{j=i+1}^{i+n-1}\binom{b_i\cdot b_j}2=\frac n2\sum_{j=1}^{n-1}\binom{b_0\cdot b_j}2 $$ Writing our initial vector as $b_0=(x_0,x_1,\dots,x_{n-1})$, with each $x_i\in \{0,1\}$, you can express the dot product $b_0\cdot b_j$ as $\sum_{k=0}^{n-1} x_kx_{k+j}$.