Suppose that M is an n × n matrix with entries given by M i j = ρ | i − j | for some ρ ∈ ( 0 , 1 ). Is it true that the matrix M is non-negative definite (or even positive definite)?I was trying to write M as A ⊤ A for some matrix A, but could not do so. Any help would be greatly appreciated.

Question

Suppose that M is an   n  ×  n matrix with entries given by      M          i      j        =      ρ                  |            i      −      j              |            for some   ρ  ∈  (  0  ,  1  ). Is it true that the matrix M is non-negative definite (or even positive definite)?I was trying to write M as       A    ⊤    A for some matrix A, but could not do so. Any help would be greatly appreciated.

ebizsavvy1txn · Accepted Answer

It is positive definite. I will prove it for the case n=3 and the general case is similar. In this case                          M        =                  (                                                    1                                            ρ                                                              ρ                  2                                                                                    ρ                                            1                                            ρ                                                                                      ρ                  2                                                            ρ                                            1                                              )                ,                                            (                                                    1                                            −                ρ                                            0                                                                    0                                            1                                            −                ρ                                                                    0                                            0                                            1                                              )                M                  (                                                    1                                            0                                            0                                                                    −                ρ                                            1                                            0                                                                    0                                            −                ρ                                            1                                              )                =                  (                                                    1                −                                  ρ                  2                                                            0                                            0                                                                    0                                            1                −                                  ρ                  2                                                            0                                                                    0                                            0                                            1                                              )                .            Therefore M is positive definite because it is congruent to   (  1  −      ρ    2    )      I          n      −      1        ⊕  1In the general case, we have   (  I  −  ρ  J  )  M  (  I  −  ρ  J      )    T    =  (  1  −      ρ    2    )      I          n      −      1        ⊕  1 where J denotes the upper triangular nilpotent Jordan block of size n. Thus   M  =  A      A    T   where                    A                            =        (        I        −        ρ        J                  )                      −            1                                    (                      1            −                          ρ              2                                            I                          n              −              1                                ⊕          1          )                                                  =        (        I        +        ρ        J        +                  ρ          2                          J          2                +        ⋯        +                  ρ                      n            −            1                                    J                      n            −            1                          )                  (                      1            −                          ρ              2                                            I                          n              −              1                                ⊕          1          )                .

Celeste Barajas · Accepted Answer

Motivated from my previous comment, we have a Cholesky decomposition   M  =      A                  T              A, where  A  =      (                            1                          ρ                                      ρ            2                                    ⋯                                      ρ                          n              −              1                                                            0                          γ                          γ          ρ                          ⋯                          γ                      ρ                          n              −              2                                                            0                          0                          γ                          …                          γ                      ρ                          n              −              3                                                            ⋮                          ⋮                          ⋮                          ⋱                          ⋮                                      0                          0                          0                          …                          γ                      )  and   γ  =      1    −          ρ      2      . For a proof, note that      A          i      j        =      ρ          j      −      i        (            1              {      i      =      1      }        +  γ            1              {      i      &amp;gt;      1      }        )            1              {      i      ≤      j      }        .Then                    [                  A                                    T                                      A                  ]                      i            j                          =                  ∑                      k                                    A                      k            i                                    A                      k            j                                              =                  ∑                      k                                    ρ                      i            +            j            −            2            k                          (                              1                                {            k            =            1            }                          +        γ                              1                                {            k            &amp;gt;            1            }                                    )          2                                      1                                {            k            ≤            min            {            i            ,            j            }            }                                                            =                  ∑                      k                                    ρ                      i            +            j            −            2            k                          (                  ρ          2                                      1                                {            k            =            1            }                          +        1        −                  ρ          2                )                              1                                {            k            ≤            min            {            i            ,            j            }            }                                                            =                  ρ                      i            +            j                          +        (        1        −                  ρ          2                )                  ∑                      k            =            1                                min            {            i            ,            j            }                                    ρ                      i            +            j            −            2            k                                                            =                  ρ                      i            +            j            −            2            min            {            i            ,            j            }                                                            =                  ρ                                    |                        i            −            j                          |                                      ,            which is precisely       M          i      j

Suppose that M is an n xx n matrix with entries given by M_(ij)=rho^(|i−j|) for some rho in (0,1). Is it true that the matrix M is non-negative definite (or even positive definite)?

Answered question

Answer & Explanation

New Questions in Precalculus