\(r\)-numbers completion problems of partial upper canonical form. I (Q1614107)

A partial upper triangular matrix \(A\) is an \(n\times n\) matrix whose elements below the main diagonal are unspecified. It is said to be in upper canonical form if all the specified elements are zero, except for the elements on positions \((j,j)\), \(j=1,\dots,\lfloor n/2\rfloor+1\), that can be arbitrary, and the elements \((j,n+1-j)\), \(j=1,\dots,\lfloor n/2\rfloor\) that are 1. Given some \(n\times m\) matrix \(B\), the completion problem is to find the unspecified elements of \(A\) such that the \(r\)-numbers \((r_1,\dots,r_n)\) for the pair \((A,B)\) have prescribed values. The \(r\)-numbers are closely related to the controllability indices and are defined as \(r_1=\text{ rank}(B)\) and \(r_j=\text{ rank} {\mathcal C}_j(A,B)-\text{ rank} {\mathcal C}_{j-1}(A,B)\), with \({\mathcal C}_j(A,B)=[B~AB~\cdots~A^{j-1}B]\), \(2\leq j\leq n\). An algorithm is described that first sets all the unspecified elements equal to 0 and then replaces some specific ones by 1. The algorithm works only under certain restrictive conditions (\(B\) has a particular form and only the first \(\lfloor n/2\rfloor\) \(r\)-numbers are prescribed, etc.). This is a constructive way of proving that in those conditions, the completion problem has indeed a solution.