  In this paper, we consider the problem of computing the rank of a
block-structured symbolic matrix (a generic partitioned matrix) $A = (A_{\alpha
\beta} x_{\alpha \beta})$, where $A_{\alpha \beta}$ is a $2 \times 2$ matrix
over a field $\mathbf{F}$ and $x_{\alpha \beta}$ is an indeterminate for
$\alpha = 1,2,\dots, \mu$ and $\beta = 1,2, \dots, \nu$. This problem can be
viewed as an algebraic generalization of the bipartite matching problem and was
considered by Iwata and Murota (1995). Recent interests in this problem lie in
the connection with non-commutative Edmonds' problem by Ivanyos, Qiao, and
Subrahamanyam (2018) and Garg, Gurvits, Oliveiva, and Wigderson (2019), where a
result by Iwata and Murota implicitly states that the rank and non-commutative
rank (nc-rank) are the same for this class of symbolic matrices.
  The main result of this paper is a simple and combinatorial $O((\mu \nu)^2
\min \{ \mu, \nu \})$-time algorithm for computing the symbolic rank of a $(2
\times 2)$-type generic partitioned matrix of size $2\mu \times 2\nu$. Our
algorithm is inspired by the Wong sequence algorithm by Ivanyos, Qiao, and
Subrahamanyam for the nc-rank of a general symbolic matrix, and requires no
blow-up operation, no field extension, and no additional care for bounding the
bit-size. Moreover it naturally provides a maximum rank completion of $A$ for
an arbitrary field $\mathbf{F}$.
