The WST-decomposition for partial matrices

A partial matrix over a field $\mathbb{F}$ is a matrix whose entries are either an element of $\mathbb{F}$ or an indeterminate and with each indeterminate only appearing once. A completion is an assignment of values in $\mathbb{F}$ to all indeterminates. Given a partial matrix, through elementary row operations and column permutation it can be decomposed into a block matrix of the form $\left[\begin{smallmatrix}{\bf W} & * & * \ 0 & {\bf S} & * \ 0 & 0 & {\bf T} \end{smallmatrix}\right]$where${\bf W}$ is wide (has more columns than rows), $\mathbf{S}$ is square, $\mathbf{T}$ is tall (has more rows than columns), and these three blocks have at least one completion with full rank. And importantly, each one of the blocks $\mathbf{W}$, $\mathbf{S}$ and $\mathbf{T}$ is unique up to elementary row operations and column permutation whenever ${\bf S}$isrequiredtobeaslargeaspossible\mathrm{.}Whenthisisthecase$\left[\begin{smallmatrix}{\bf W} & * & * \ 0 & {\bf S} & * \ 0 & 0 & {\bf T} \end{smallmatrix}\right]$ will be called a WST-decomposition. With this decomposition it is trivial to compute maximum rank of a completion of the original partial matrix: $#\mbox{rows}({\bf W})+#\mbox{rows}({\bf S})+#\mbox{cols}({\bf T})$. In fact we introduce the WST-decomposition for a broader class of matrices: the ACI-matrices.