Dena Plant and Dr. Wayne Barrett, Mathematics

As our research began we focused on proving the hypothesis that for a 4 x 4 Positive Definite matrix A, the ratio

where |123| is the determinant of the submatrix of A defined by the rows and columns 1, 2 and 3 (others are similar).

Although we were able to uncover useful results while trying to prove this theorem, it soon became clear that the problem was too complicated to be solved with the time and resources allotted.

In order to effectively use the ORCA funding we decided to explore another problem in the field of matrix analysis. The following problem explores relationships between matrix analysis and graph theory.

Let G be a graph on n vertices, and let G c be the compliment of G. Let A be the n x n matrix such that if the edge ij ( for i doesn’t = j; 1 < i < n ; 1 < j < n) exists in G c then the entry aij = 1, and for i = j, aij = 1. Any open entries are filled with values that minimize the resulting eigenvalues. Then the maximum of these eigenvalues is 0(G).

For example:

We explored several graphs with vertices from n=2 to n=8. We found the A matrix for each graph by analyzing the edges of the compliment and assigning values to the undetermined entries through analysis and elimination. Our goal was to find the A matrices and explore the similarities and patterns that occur between different graphs and matrices.

During our research we were able to identify several significant patterns that occur in such matrices. Although we were able to discover many patterns, the following three are the most significant of our findings.

First, consider the case when the graph G yields a matrix in which only the two off diagonal corner entries are undefined. In other words, the case in which G has only one edge. Then the following assignment of the matrix yields the desired result. Let A in Mn(R) be the matrix with all entries equal to 1 except for a1n and an1 which equal –(n-2). We were able to prove that in this case the eigenvalues of A are always equal to 0 (n-3 times), -(n-2), and n-1 (2 times). Hence q(G) = n-1. This is correct since

for every n. Hence filling the undefined entries with –(n-2) always yields the correct q(G).

Second, consider the case where G yields an n x n matrix (n ³ 5) in which the three entries of the off diagonal corners are undefined. (For example, Let n = 5. Then A = [[1,1,1,x,z], [1,1,1,1,y], [1,1,1,1,1], [x,1,1,1,1], [z,y,1,1,1].) These are graphs with complements in the form of the gem such as K3 – K3 – K3, and K4 – K4 – K4. In such cases the following assignment will yield the correct q(G).

Let the corner entries z = 1. Let the off corner undefined entries equal –(n-3). (Hence for n=5, A = [[1,1,1,-2,1], [1,1,1,1,-2], [1,1,1,1,1], [-2,1,1,1,1], [1,-2,1,1,1]].) Then the nonzero eigenvalues of this matrix are always –(n-4), -(n-2), and n-2 (3 times), and q(G) = n-2 as desired. Third, let G be a graph that yields a matrix of the same form as those in the second case. After spending much time exploring the eigenvalues of theses matrices we decided to study the eigenvectors that produce the eigenvalues. It was determined that the eigenvectors that correspond to the largest eigenvalue, n-2, are representative of the cliques of the graph in the form of the indicator function. For instance, the 5 x 5 graph K3 – K3 – K3 has eigenvectors [1,1,1,0,0], [0,1,1,1,0], [0,0,1,1,1] for the eigenvalues equal to 3. Hence the eigenvectors have the form of 1K(x) = {1, xÎ K; 0, xÎ K}, which correspond to the three cliques of the graph. Using Maple we were able to determine that this pattern also holds true for larger graphs of similar form such as K4 – K4 – K4. (There also appear to be patterns between the other less significant eigenvectors)

It is helpful to note that we were also able to determine that the chosen variable entries of the A matrices are not necessarily unique in all cases. In fact, there are often several variables that can be selected in order to meet the guidelines required and yield the correct q(G). However, some choices are superior to others in the fact that patterns can be drawn from them, and graphs with a different n can be solved in a similar manner. In further study it would be interesting to explore these different possibilities. It would also be interesting to determine which graphs have only one solution.

These findings are encouraging and lead us to believe that further study of these matrices would be advantageous. We are confident that given sufficient time and effort this problem will yield results worth more in depth analysis and perhaps publication