2
$\begingroup$

Let $A \in \mathbb{R}^{n \times n}$ be a bidiagonal matrix with non zero elements on its diagonal and super diagonal. Let $B$ be defined as $$B=\begin{bmatrix}0&{A} \\{A}^T &0 \end{bmatrix}$$.

Find permutation matrix $P$ such that $C=PBP^T$ is a tridiagonal matrix.

I noticed that permutation matrices with only row exchanges did not satisfy this condition. I am unable to find a way to determine a non-symmetric permutation matrix that converts $B$ into a tridiagonal matrix.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ are you sure they always exist? it is not hard to check cases n<5 on computer. $\endgroup$
    – Dima Pasechnik
    Commented Dec 6, 2019 at 9:59
  • $\begingroup$ Looks a lot like an exercise, which would be off-topic here. $\endgroup$
    – Federico Poloni
    Commented Dec 6, 2019 at 11:37

1 Answer 1

Reset to default
2
$\begingroup$

The permutation matrix $P$ corresponding to the permutation $$ \sigma \colon \begin{cases} i \mapsto 2i & \text{ if } i \in [1,n] \\ i \mapsto 2i - 2n - 1 & \text{ if } i \in [n+1,2n] \end{cases} $$ does the job.

Edit: As requested, I am providing some details. Notice that the original matrix $B$ has zero diagonal, which implies that $C$ also has zero diagonal, i.e., it has a non-zero subdiagonal and a non-zero superdiagonal but zeros everywhere else. There are precisely $4n-2$ non-zero entries in $B$ and also precisely $4n-2$ non-zero entries in the matrix $C$ we are looking for. We have (for $n=4$, for example) $$ B = \begin{pmatrix} &&&& \color{red}{*} & \color{red}{*} && \\ &&&&& \color{red}{*} & \color{red}{*} & \\ &&&&&& \color{red}{*} & \color{red}{*} \\ &&&&&&& \color{red}{*} \\ \color{blue}{*} &&&&&&& \\ \color{blue}{*} & \color{blue}{*} &&&&&& \\ & \color{blue}{*} & \color{blue}{*} &&&&& \\ && \color{blue}{*} & \color{blue}{*} &&&& \end{pmatrix}$$ and the permutation $\sigma$ transforms $B$ into the matrix $$ C = \begin{pmatrix} & \color{blue}{*} &&&&&& \\ \color{red}{*} && \color{red}{*} &&&&& \\ & \color{blue}{*} && \color{blue}{*} &&&& \\ && \color{red}{*} && \color{red}{*} &&& \\ &&& \color{blue}{*} && \color{blue}{*} && \\ &&&& \color{red}{*} && \color{red}{*} & \\ &&&&& \color{blue}{*} && \color{blue}{*} \\ &&&&&& \color{red}{*} & \\ \end{pmatrix}.$$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yes, this works, would you let me know the steps that you took to arrive at this? $\endgroup$
    – Prashant Govindarajan
    Commented Dec 6, 2019 at 10:59
  • $\begingroup$ I don't see how $\sigma$ does the job. Indeed, $\sigma B\sigma^\top$ has the same block structure as $B$, with 0 blocks in upper leat and bottom right cornes, $\endgroup$
    – Dima Pasechnik
    Commented Dec 6, 2019 at 12:29
  • $\begingroup$ I have now edited the answer to provide more details; I hope this is clearer now. $\endgroup$
    – Tom De Medts
    Commented Dec 6, 2019 at 16:33
  • $\begingroup$ @TomDeMedts - right, I misread your formula. $\endgroup$
    – Dima Pasechnik
    Commented Dec 6, 2019 at 17:57

Not the answer you're looking for? Browse other questions tagged .