0
$\begingroup$

From Wikipedia, a symmetric matrix is a square matrix that is equal to its transpose. An example of this (I think) is an adjacency matrix with undirected edges, which is a square matrix representing links between elements (undirected in this case).

The thing is, the data is duplicated in this case (looking at it from a computer science perspective). The two halves of the diagonal carry the same information, so you can just use one half of it.

I am new to matrices, so I apologize if this is a basic question. The question is if there is any advantage mathematically or from a computer science perspective to representing data (such as graphs, but more generically any data such as key/value pairs or pointers, etc.) using symmetric matrices like this. Wondering if it (for example) makes lookup O(1) in certain cases, or it provides some other significant hidden benefit because of the symmetry.

$\endgroup$
1
$\begingroup$

The main advantages of matrices are in solving linear equations. In fact judging whether there even exists solutions to a system of equations becomes very easy when you represent equations in form of matrices. Matrices form the core of Linear Algebra.

Systems of linear equations pop up everywhere in the real world. Linear Algebra is integral to Machine Learning, Image processing, Computer Graphics, Operations Research.....( the list is inexhaustible).

Using matrices as representation of graphs is in fact one of the less useful facets of Linear Algebra (due to the more space efficient Adjacency List data structures). If we talk about using matrices as datastructures you can look into Bottom Up approach of solving dynamic programming problems.

Importance of Symmetric Matrices

If we have a symmetric matrix, then we immediately know a few things about the concerned system of linear equations:

  • If each vector is linearly independent, then we have as many pivots as we have rows or columns.
  • This is a special case where we say that the matrix has a full rank. Hence the matrix is invertible, and there exists a particular unique solution to this system of linear equations.
  • Eigen Values are defined for square matrices.
  • This allows us to investigate whether a given matrix is diagonalizable. If the matrix is diagonalizable, then it allows us to perform efficient computations of the powers of A, leading into matrix exponentials.
  • Diagonalization is a very common mathematical operation in quantum mechanics. The time-independent Schrödinger equation is broadly speaking, an eigenvalue equation.

Since matrices are nothing but representations of linear equations, we cannot force ourselves to represent data symmetrically (actually we can, and often do). If a particular dataset that we are investigating has the same number of vectors as its attributes (which is definitely coincidental) then we can perform an extended analysis on the dataset owing to the properties of the square matrix.

$\endgroup$
  • $\begingroup$ I understand that matrices are the basis of linear algebra and understand the wide applicability of linear algebra in computer science, as well as solving linear constraint equations, etc. I'm wondering specifically about symmetric integer matrices, specifically wondering what advantages you gain by having the symmetric property. $\endgroup$ – Lance Pollard Apr 21 '18 at 3:18
  • 1
    $\begingroup$ There you go. Added a new section on symmetric matrices. $\endgroup$ – Sagnik Apr 21 '18 at 3:44
0
$\begingroup$

I will assume that you are talking about real matrices.

Theorem: Let $T$ be a linear operator on a finite-dimensional real inner product space $V$. Then $T$ is self-adjoint iff there exists an orthonormal basis $\beta$ for $V$ consisting of eigenvectors of T.

And for your information, an operator on a inner product space whose dimension is $n$ can be written as a matrix based on the selection of basis.

Therefore, if we can represents a matrix $M$ in a symmetric form (self-adjoint is in some ways equivalent to symmetric when $F = R$), then this matrix can be diagonalized, which is a nice form for computation, e.g., do "power of the matrix".

But how do we apply the rapid version of "power of the matrix" to computer science? Well, consider the computer graphic area. We know that apply an matrix to a vector can be seen as a linear transformation to something in your screen. With the diagonalized matrix, we can improve the graphic efficiency a lot.

$\endgroup$
  • $\begingroup$ If the type of matrix is of concern, I would like to focus on integer matrices :) $\endgroup$ – Lance Pollard Apr 21 '18 at 2:10
  • 1
    $\begingroup$ @LancePollard Since integers are on real field, my statement still holds :) $\endgroup$ – Wen Apr 21 '18 at 2:11
  • $\begingroup$ Wondering how you know diagonalization is a nice form for computation. From a quick search the "power of the matrix" is easily computed on a diagonalized matrix, but I don't see an application for that outside pure math. $\endgroup$ – Lance Pollard Apr 21 '18 at 2:13
  • $\begingroup$ @LancePollard Well I add something new to the end of my post. Hope this will help $\endgroup$ – Wen Apr 21 '18 at 2:18

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.