Using Mathematica to Automatically Reveal Matrix Structure

Question

I spend a lot of time looking at larger matrices (10x10, 20x20, etc) which usually have some structure, but it is difficult to quickly determine the structure of them as they get larger. Ideally, I'd like to have Mathematica automatically generate some representation of a matrix that will highlight its structure. For instance,

(A = {{1, 2 + 3 I}, {2 - 3 I, 4}}) // StructureForm

would give

{{a, b}, {Conjugate[b], c}}

or even

{{a, b + c I}, {b - c I, d}}

is acceptable. A somewhat naive implementation

StructureForm[M_?MatrixQ] := 
  MatrixForm @ Module[
    {pos, chars},
    pos = Reap[
           Map[Sow[Position[M, #1], #1] &, M, {2}], _, 
           Union[Flatten[#2, 1]] &
          ][[2]];  (* establishes equality relationship *)
    chars = CharacterRange["a", "z"][[;; Length @ pos ]];
    SparseArray[Flatten[Thread /@ Thread[pos -> chars] ], Dimensions[M]]
  ]

works only for real numeric matrices, e.g.

StructureForm @ {{1, 2}, {2, 3}} == {{a, b}, {b, c}}

Obviously, I need to define what relationships I think may exist (equality, negation, conjugate, negative conjugate, etc.), but I'm not sure how to establish that these relationships exist, at least in a clean manner. And, once I have the relationships, the next question is how to determine which is the simplest, in some sense? Any thoughts?

One possibility that comes to mind is for each pair of elements generate a triple relating their positions, like {{1,2}, Conjugate, {2,1}} for A, above, then it becomes amenable to graph algorithms.

Edit: Incidentally, my inspiration is from the Matrix Algorithms series (1, 2) by Stewart.

Might be hard in general. For structure checking e.g. is it Hermitian with symbolic variables assumed real, could use as a utility something like SameQ[mat,ComplexExpand[Conjugate[Transpose[mat]]]]. If you work with explicit Re and Im then built in HermitianMatrixQ may also be of some use. Likewise SymmetricMatrixQ. — Daniel Lichtblau
@Daniel, I knew it wasn't easy, but I thought I'd ask. Both HermitianMatrixQ and SymmetricMatrixQ are nice, and would be useful in displaying matrices with only those types of symmetry. Unfortunately, as is often the case, the matrices I work with usually have more complicated symmetries, in addition to be Hermitian, and I'd like a tool that can display such structure. Definitely not a simple request. — rcollyer
@Daniel, also, MatrixPlot and ArrayPlot are sometimes useful, but they don't reveal the structure of symbolic matrices, and it is difficult to use them to determine hermiticity. Ideally, I'd like to perform one test to more clearly reveal the structure, and the current tools require multiple tests. — rcollyer
I wonder, if two pieces of the matrix have some numerical similarity that does not necessarily imply they are part of the same structure, does it? See RotationMatrix[a] // structureForm ==> {{"a", "b"}, {-"b", "a"}}, whereas RotationMatrix[[Pi]/4] // structureForm ==> {{"a", -"a"}, {"a", "a"}} and RotationMatrix[[Pi]/8] // structureForm ==> {{"a", "b"}, {-"b", "a"}} — Sjoerd C. de Vries
@Sjoerd, in the examples you gave, all the matrices are orthogonal, so they have the same structure. Therefor, the pieces of the matrix must have some prescribed numerical similarity. — rcollyer

WReach WReach · Accepted Answer · 2011-04-03T17:19:22

We can start by defining the relationships that we want to recognize:

ClearAll@relationship
relationship[a_ -> sA_, b_ -> sB_] /; b == a := b -> sA
relationship[a_ -> sA_, b_ -> sB_] /; b == -a := b -> -sA
relationship[a_ -> sA_, b_ -> sB_] /; b == Conjugate[a] := b -> SuperStar[sA]
relationship[a_ -> sA_, b_ -> sB_] /; b == -Conjugate[a] := b -> -SuperStar[sA]
relationship[_, _] := Sequence[]

The form in which these relationships are expressed is convenient for the definition of structureForm:

ClearAll@structureForm
structureForm[matrix_?MatrixQ] :=
  Module[{values, rules, pairs, inferences}
  , values = matrix // Flatten // DeleteDuplicates
  ; rules = Thread[Rule[values, CharacterRange["a", "z"][[;; Length@values]]]]
  ; pairs = rules[[#]]& /@ Select[Tuples[Range[Length@values], 2], #[[1]] < #[[2]]&]
  ; inferences = relationship @@@ pairs
  ; matrix /. inferences ~Join~ rules
  ]

In a nutshell, this function checks each possible pair of values in the matrix inferring a substitution rule whenever a pair matches a defined relationship. Note how the relationship definitions are expressed in terms of pairs of substitution rules in the form value -> name. Matrix values are assigned letter names, proceeding from left-to-right, top-to-bottom. Redundant inferred relationships are ignored assuming a precedence in that same order.

Beware that the function will run out of names after it finds 26 distinct values -- an alternate name-assignment strategy will be needed if that is an issue. Also, the names are being represented as strings instead of symbols. This conveniently dodges any unwanted bindings of the single-letter symbols names. If symbols are preferred, it would be trivial to apply the Symbol function to each name.

Here are some sample uses of the function:

In[31]:= structureForm @ {{1, 2 + 3 I}, {2 - 3 I, 4}}

Out[31]= {{"a", "b"}, {SuperStar["b"], "d"}}

In[32]:= $m = a + b I /. a | b :> RandomInteger[{-2, 2}, {10, 10}];
         $m // MatrixForm
         $m // structureForm // MatrixForm

enter image description here

Using Mathematica to Automatically Reveal Matrix Structure

2 Answers