How to get elements corresponding to UpperTriangularize

Question

For a generally non-square matrix M, I want the upper triangle that include the diagonal entries. Specifically, this is implemented via UpperTriangularize:

MatrixForm[UpperTriangularize[{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}]]

yields the matrix

$$\begin{pmatrix} 1&2&3\\0&5&6\\0&0&9 \end{pmatrix}.$$

Note, as per the documentation UpperTriangularize can also apply to non-diagonal matrices. Given the dimensions of the matrix, I want to return elements of the matrix that correspond to non-zero values of the resulting UpperTriangularize matrix.

This requires extending this solution to non-diagonal matrices and with the diagonal matrices. Any suggestions?

The desired output is a list of matrix elements that are non-zero. I.e. for a 3 by 3 matrix this should be the output:

{{1,1},{1,2},{1,3},...,{2,2},{2,3},...,{3,3}}

This should be generalised to the dimensions of the matrix. For this example, I'm currently using

Flatten[Append[{Subsets[Range[3], {2}]}, Table[{i, i}, {i, 1, 3}]], 1]

Wondering if there is a better approach.

Answer 1

Update: To get the position indices of the upper triangular part:

mat = Partition[Range[9], 3];

Tuples

Select[Apply @ LessEqual][Tuples[Range /@ Dimensions[#]]] & @ mat

{{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}}

SparseArray

Sort@SparseArray[{i_, j_} /; i <= j -> 1, Dimensions@#]["NonzeroPositions"] & @ mat

{{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}}

SparseArray[UpperTriangularize @ ConstantArray[1, Dimensions @ #]] 
    ["NonzeroPositions"]& @ mat 

{{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}}

Table

 Join @@ Table[{i, j}, {i, First@Dimensions[#]}, {j, i, Last@Dimensions[#]}] & @ mat

{{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}}

Position

Position[UpperTriangularize[ConstantArray[1, Dimensions @ #]], 1, 
  Heads -> False] & @ mat

{{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}}

MapIndexed

Join @@ MapIndexed[If[# == 0, Nothing, #2] &, 
   UpperTriangularize @ ConstantArray[1, Dimensions@#], {2}] & @ mat

{{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}}

Original answer:

mat = Partition[Range[25], 5];

Row[MatrixForm /@ {mat, UpperTriangularize @ mat}, Spacer[10]]

MapIndexed[#[[#2[[1]] ;;]] &] @ mat

 {{1, 2, 3, 4, 5}, {7, 8, 9, 10}, {13, 14, 15}, {19, 20}, {25}}

If you want to get a single list:

MapIndexed[## & @@ #[[#2[[1]] ;;]] &] @ mat

{1, 2, 3, 4, 5, 7, 8, 9, 10, 13, 14, 15, 19, 20, 25}

Few additional alternatives:

MapIndexed[Drop[#, #2[[1]] - 1] &] @ mat

 {{1, 2, 3, 4, 5}, {7, 8, 9, 10}, {13, 14, 15}, {19, 20}, {25}}

MapIndexed[Take[#, #2[[1]] - 1 - Length @ #] &] @ mat

 {{1, 2, 3, 4, 5}, {7, 8, 9, 10}, {13, 14, 15}, {19, 20}, {25}}

Pick[#, UpperTriangularize@ ConstantArray[1, Dimensions@#], 1] & @ mat

 {{1, 2, 3, 4, 5}, {7, 8, 9, 10}, {13, 14, 15}, {19, 20}, {25}}

If you need a single list, wrap the functions above with Apply[Join] or Flatten:

Join @@ MapIndexed[Drop[#, #2[[1]] - 1] &]@mat

 {1, 2, 3, 4, 5, 7, 8, 9, 10, 13, 14, 15, 19, 20, 25}

If the upper triangular part does not contain zeros (as in mat) you can also use SparseArray and extract "NonzeroValues":

SparseArray[UpperTriangularize @ #]["NonzeroValues"] & @ mat 

 {1, 2, 3, 4, 5, 7, 8, 9, 10, 13, 14, 15, 19, 20, 25}

Answer 2

(This answer was written before it became clear that the expected output is a list of positions. This answer is about how to retrieve the elements.)

Here's an implementation that support the second argument of UpperTriangularize:

upperTriangularElements[m_] := upperTriangularElements[m, 0]
upperTriangularElements[m_, k_] := Module[{nr, nc},
  {nr, nc} = Dimensions[m];
  Fold[
   #~Join~Diagonal[m, #2] &,
   {},
   Range[k, nc - 1]
   ]
  ]

m = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
m // MatrixForm

upperTriangularElements[m]

{1, 5, 9, 2, 6, 3}

upperTriangularElements[m, 1]

{2, 6, 3}

This function also works for non-square matrices.

Answer 3

(ArrayRules@UpperTriangularize[Partition[Range[9],3]])[[All,1]] // Most

{{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}}

(ArrayRules@UpperTriangularize[Partition[Range[12],4]])[[All,1]] // Most

{{1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}, {2, 3}, {2, 4}, {3, 3}, {3, 4}}