1
$\begingroup$

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?

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

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.

$\endgroup$
4
  • $\begingroup$ Thanks a lot. That was helpful. $\endgroup$
    – Sadguru
    Nov 18 '17 at 8:48
  • $\begingroup$ $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? $\endgroup$
    – user91684
    Nov 18 '17 at 9:27
  • $\begingroup$ You show that $rank(\Lambda)\geq 1$, that is true. $\endgroup$
    – user91684
    Nov 18 '17 at 9:58
  • $\begingroup$ 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. $\endgroup$ Nov 18 '17 at 12:17
1
$\begingroup$

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$.

$\endgroup$
3
  • 1
    $\begingroup$ Still, $A$ has a very specific form. Can't this be exploited to particularize the solution? $\endgroup$ Nov 18 '17 at 12:33
  • $\begingroup$ 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$. $\endgroup$
    – Sadguru
    Nov 18 '17 at 12:57
  • $\begingroup$ Sorry. The example is supposed to be read as $2 [1 \quad 1] = [1 \quad 0.5] + [1 \quad 1.5].$ $\endgroup$
    – Sadguru
    Nov 18 '17 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.