1
$\begingroup$

Say I am given the $0/1$ adjacency matrix of an undirected graph. Also I am given a representation $\rho$ of some group $G$ and an orientation has been arbitrarily chosen along each edge. Let $E^{oriented}$ be the set of edges of the graph where for each edge one has chosen an orientation i.e choosing to denote a particular edge as $(a,b)$ instead of $(b,a)$ (its an independent choice at each edge) And I am given a map $s:E^{orient} \rightarrow \rho(G)$.

Now construct a matrix $B$ thought of as a $\vert V \vert \times \vert V \vert$ sized array of $dim(\rho)$ dimensional matrices such that the $B$ matrix's $(i,j)$ array position is

$= s((i,j))$ if $(i,j) \in E^{orient}$

$= s((j,i))^{-1}$ if $(i,j) \not \in E^{orient}$ but $(j,i) \in E^{orient}$

$=$ a $0$ matrix of $dim(\rho)$ if neither $(i,j)$ nor $(j,i)$ is in $E^{orient}$.

Clearly $B$ is a $dim(\rho) \vert V \vert$ dimensional matrix.

  • Is there a short-cut or any simplification that can be done in calculating the characteristic polynomial of $B$ ? (than the obvious brute-force calculation of the determinant of a $dim(\rho) \vert V \vert$ dimensional matrix)
Improve this question
$\endgroup$
6
  • $\begingroup$ Have you looked at any of the literature on computing characteristic polynomials for graphs (i.e. the special case where the representation $\rho$ is trivial)? I'm not an expert but from a google search it seems that there are specialized algorithms for that case, and maybe some of them generalize... $\endgroup$
    – j.c.
    Commented May 7, 2015 at 19:50
  • 1
    $\begingroup$ I wasn't aware anything like that is there. Here all the non-triviality is in the $\rho$. Even a small dimensional represenatation on a small graph is multiplying up to give a huge matrix! $\endgroup$
    – user6818
    Commented May 7, 2015 at 22:04
  • $\begingroup$ You're right, I had the wrong picture in mind. Sorry. $\endgroup$
    – j.c.
    Commented May 7, 2015 at 22:38
  • 1
    $\begingroup$ @Kimball I have clarified the point in an edit of the question. Does that help? True that this B is a matrix made up of orthogonal blocks - and is something known about the characteristic polynomials of such? (something that can help shorten the calculation load!) $\endgroup$
    – user6818
    Commented May 8, 2015 at 17:25
  • $\begingroup$ @user6818 I don't know a lot about computing characteristic polynomials, but maybe there are some methods for block matrices. At least looking at the blocks seems potentially useful for computing traces of powers of $B$. $\endgroup$
    – Kimball
    Commented May 9, 2015 at 0:59

0

Reset to default

You must log in to answer this question.