# A matrix completion problem

In their paper, Corners of normal matrices, Rajendra Bhatia and Man-Duen Choi asked the following question:

Given a matrix pair $$(B,C)$$ where $$B,C∈M_n$$, does there exist matrices $$A,D ∈ M_n$$ such that the block matrix: $$N = \begin{bmatrix} A & B \\ C & D \end{bmatrix}$$ is normal.

I have made some progress on this problem by constructing explicit normal matrices of the form above for certain pairs of matrices $$(B,C)$$ that do not appear in the literature. One open question in the paper is whether or not the quantity $$α_n=\sup\{\frac{||B||}{||C||}:∃A,D ∈ M_n$$ such that N is normal $$\}$$ is bounded. Moreover, they prove that $$α_n < \sqrt{n}$$ for $$n > 4$$. I suspect that $$α_n$$ is unbounded but I can only get that $$α_n \geq \sqrt{2}$$. Does anyone have any ideas here?

Edit after setting the bounty

What I am looking for, if it exists, is a sequence of $$n \times n$$ matrices, $$A_n, B_n, C_n, D_n$$ such that when you put them in the matrix configuration above, the resulting matrix is normal and $$\frac{||B_n||}{||C_n||} \to \infty$$ as $$n \to \infty$$. Alternatively, if you can prove that my intuition is wrong, i.e. show that $$\alpha_n$$ is bounded, then you will also receive the bounty.

Second Edit The norm we are considering here is the usual operator norm.

• Well, you can get $\alpha_n \geq \sqrt{3}$ for all $n \geq 3$ just by embedding the $6\times 6$ matrix from that paper in a $2n\times 2n$ matrix, padding with zeros appropriately. Feb 27, 2014 at 23:37
• @ Nathaniel, can I iterate to get something even better? Feb 28, 2014 at 6:02
• What kind of restrictions would you like to impose? There are no solutions for $n=1$, $C=0$ and $B\ne0$ for example... Jul 28, 2014 at 6:24
• How much important is that $A$ and $D$ have same size, that is $B$ and $C$ are square matrices ? Jan 21, 2017 at 12:14
• @MustafaSaid Do you agree with my edits? May 5 at 8:40

The value of $\alpha_n$ is not bounded for many naturally defined norms on $\mathbb{C}^{n\times n}$, including those induced from $L^p$ norms on $\mathbb{C}^n$ with $p\neq2$. Denoting these norms by $\|\cdot\|_p$, I give an example of a normal matrix $\left(\begin{smallmatrix}F&G\\H&K\end{smallmatrix}\right)$ which consists of four $n\times n$ blocks and satisfies $\|G\|_p/\|H\|_p\in\Theta\left(n^{(p-2)/4p}\right)$.

For $A\in\mathbb{R}^{r\times r}$, denote by $A^{\otimes k}$ the matrix with rows and columns labeled by $\{1,\ldots,r\}^k$ defined as $A_{i_1...i_k}^{j_1...j_k}=A_{i_1}^{j_1}...A_{i_k}^{j_k}$. Clearly, $A^{\otimes k}$ is normal if $A$ is normal.

Now let $A$ be the normal matrix $$\begin{pmatrix}0&0&\sqrt{2}&0\\1&0&0&0\\0&1&0&1\\1&0&0&0\end{pmatrix}$$ from the cited paper. Then, the $(1...1)$ row of $A^{\otimes2k}$ has a unique nonzero entry $2^k$ while the $(1...1)$ column of $A^{\otimes2k}$ has $2^{2k}$ nonzero entries all equal to $1$. So we can get a sequence of normal matrices $\left(\begin{smallmatrix}O_{1\times1}&Q_{1\times n}\\R_{n\times 1}&S_{1\times n}\end{smallmatrix}\right)$ which have size $16^k\times16^k$ and satisfy $\|Q\|_p=2^k$, $\|R\|_p=2^{2k/p}$. Finally, we can note that $\left(\begin{smallmatrix}I&O\\O&N\end{smallmatrix}\right)$ is normal when $N$ is normal, so it is not a problem that $Q$ and $R$ are not square.

UPD. This answer was posted before the second edit.

• On a skim of the Bhatia-Choi paper, it looks like $|A|$ denotes the first singular value of $A$, equal to $\mathrm{sup}_{|x|=1} |Ax|$, not to $\mathrm{sup}_{ij} |A_{ij}|$. Or am I missing something? Jul 30, 2014 at 20:36
• @DavidSpeyer Thank you for the comment, I have edited my answer accordingly
– user56203
Jul 30, 2014 at 21:14
• The operator norm induced by $\|\cdot \|_{\infty}$ is $\max_j \sum_k |B_{jk}|$ (maximal row sum). It appears this is not what you're looking at here (if I understand your argument correctly, which perhaps I don't). Jul 31, 2014 at 3:00
• @ChristianRemling Thanks for the comment, I still believe that the argument is correct but I edited my post. I described $A^{\otimes k}$ more explicitly and generalized the result to a larger family of norms
– user56203
Jul 31, 2014 at 9:15
• We are interested in the usual euclidean operator norm in this question. Aug 1, 2014 at 13:44