Consider the equation $\lambda * T * \lambda = A$ where $T$ is a $m\times m$ $0/1$ upper triangular matrix and $A$ is a $m\times m$ matrix with every entry being $n$, i.e. $A$ is rank one matrix. I want to solve for the matrix $\lambda$. Since $A$ is rank one and given that $T$ is full rank, it is clear that $\lambda$ is also a rank one matrix. Is there a simpler way of finding what $\lambda$ is without having to solve the equations?

• Clearly $rank(\Lambda)=1$; are you sure?
– user91684
Nov 18 '17 at 9:31
• Sorry. I was wrong. It is $rank(\Lambda) \geq 1$. Nov 18 '17 at 12:40

With these constraints, your matrix $\lambda$ (I suggest you use the notation $\Lambda$ instead, because $\lambda$ usually denotes a scalar) must be of the form $c \mathbf{1}\mathbf{1}^T$, where $\mathbf{1}$ is a vector having all entries equal to one. This is because the columns of $A$, which you defined as being all equal to $n\mathbf{1}$, are all linear combinations of the columns of $\Lambda$, and the same goes for the rows of $A$, which are all given by $n\mathbf{1}^T$ (note that $A = n \mathbf{1} \mathbf{1}^T$).

All that is left is to compute the constant $c$. You have: $$\Lambda T \Lambda = c^2 \mathbf{1} \mathbf{1}^T T \mathbf{1} \mathbf{1}^T = n \mathbf{1} \mathbf{1}^T.$$

It is easy to see that $\mathbf{1}^T T \mathbf{1}$ yields the sum of all entries of $T$ (let's denotes it by $t$), and so we can deduce: $$c^2 t = n,$$ i.e., $c = \sqrt{\frac{n}{t}}$.

Edit: As pointed by loup blanc, the rank of $\Lambda$ is not necessarily one. Hence it can have a more general form.

• Thanks a lot. That was helpful. Nov 18 '17 at 8:48
• $rank(\Lambda)=1$ why? A rank 1 matrix is in the form $c11^T$; are you sure? Your $t$ is non zero; it's true but why?
– user91684
Nov 18 '17 at 9:27
• You show that $rank(\Lambda)\geq 1$, that is true.
– user91684
Nov 18 '17 at 9:58
• Well, if all entries of $A$ are equal to $n$, this means $A = n 1 1^T$. But he columns of $A$ are combinations of columns of $\Lambda$ and the same goes for the rows. But you're right about the rank of $\Lambda$, I overlooked that claim. Nov 18 '17 at 12:17

Here $T=I+N$ where $N$ is a $0-1$ strictly upper triangular matrix. Our equation is equivalent to $(\Lambda T)^2=AT$ where $rank(AT)=rank(A)=1$. Note that $tr(AT)=u\geq tr(A)>0$; then, there is $P$ invertible s.t. $AT=P diag(u,0_{m-1}) P^{-1}$.

We deduce easily that $\Lambda T=Pdiag(\pm\sqrt{u},M)P^{-1}$ where $M^2=0_{m-1}$. Finally

$\Lambda=Pdiag(\pm\sqrt{u},M)P^{-1}T^{-1}$ where $P$ is fixed and $M$ satisfies $M^2=0$.

EDIT. Yes, we can explicitly calculate such a matrix $P$. Its first column is the eigenvector $[1,\cdots,1]^T$ of $AT$. Their $m-1$ last columns are constitued with a basis of $\ker(AT)$, the equation of which, being $\sum_ir_ix_i=0$ where $r_i>0$ is the sum of the entries of the $i^{th}$ column of $T$. Finally, the required $m-1$ vectors are (for example)

$x_i=-r_{i+1},x_{i+1}=r_i$ the others $x_j$ being zero, for $i=1,\cdots,m-1$.

• Still, $A$ has a very specific form. Can't this be exploited to particularize the solution? Nov 18 '17 at 12:33
• Hi. I think the specific form of $A$ does not imply that rows and columns of $\Lambda$ are of the form $c\textbf{1}^T$ and $c\textbf{1}$. As an example consider $2[1,1] = [1 0.5] + [1 1.5]$. If the claim about the rows and columns of $\Lambda$ is true, i.e., they are of the form $c\textbf{1}^T$ and $c\textbf{1}$, then we must be able to express $[1 0.5] + [1 1.5]$ as $c_1 [1 1] + c_2 [1 1]$ such that $c_1+c_2 =2$. Nov 18 '17 at 12:57
• Sorry. The example is supposed to be read as $2 [1 \quad 1] = [1 \quad 0.5] + [1 \quad 1.5].$ Nov 18 '17 at 13:05