4
votes
1answer
453 views

Surprising connection between linear algebra and graph theory

What is the intuition for linear algebra being such an effective tool to resolve questions regarding graphs? For example, one can determine if a given graph is connected by computing its Laplacian ...
0
votes
1answer
143 views

Kneser graphs eigenvalues

Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...
0
votes
0answers
64 views

Heat equation with graph laplacian

I would like to start with considering the time-dependent heat equation on a connected graph and consider its Laplacian matrix. Suppose we have a connected graph with unknown temperature on vertices. ...
2
votes
0answers
59 views

Characterize the equivalence class of bipartite graphs obtained from each other by elementary row operations on their adjacency matrices

Let $M$ be an $m\times n$ matrix real matrix. Let $G$ be a bipartite graph, with partitions $A$ and $B$, such that $|A|=m$ and $|B|=n$. A node $i\in A$ is linked to a node $j\in B$ if and only if ...
1
vote
1answer
92 views

Neighborhood overlap matrix for a bipartite graph

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap ...
0
votes
0answers
79 views

The largest size of a boolean subgraph (a hypercube) of a given graph

Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...
3
votes
1answer
109 views

The spectral radius of a modified graph

Let $H$ be a graph and let $G=H \vee K_{1}$ be obtained by creating a new vertex and joining it to every vertex in $H$. This situation has many different names: $G$ is called the cone or the ...
3
votes
1answer
180 views

Calculating a generalized inverse (Moore–Penrose pseudoinverse)

I am considering a graph with $n$ edges with the following nicely structured adjacency matrix: \begin{equation} A_n= \begin{pmatrix} 0 & 0 & 0 &\cdots & 0 & 0 & 1\\ 0 & 0 ...
3
votes
1answer
192 views

Equivalence of Hadamard Graph and Hadamard Matrix

I'm reading Distance Regular Graphs by Brouwer, Cohen, and Neumaier. In section 1.8, they explained Hadamard graphs. Conversion from a Hadamard Matrix into a Hadamard Graph An $n$-Hadamard graph $G$ ...
2
votes
1answer
180 views

Graph of Grassmannian

Let p be an integer, and let G be the graph $(V=Gr(k,\mathbb{F}_q ^n),E)$ where: $Gr(k,\mathbb{F}_q ^n)$ is the set of all subspace of $\mathbb{F}_q$ of dimension k, and $E=\{ W_1,W_2 \in V | ...
7
votes
0answers
187 views

Coherence between different ranking methods of a graph's vertices

Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher. Two natural ways of doing it are: By the degrees. By the entries in a ...
0
votes
0answers
65 views

Constructing a digraph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
2
votes
1answer
167 views

positive semidefinite matrix condition

There is a great work of Alizadeh that in section 4 speaks about Minimizing sum of the first few(k-largest) eigenvalues of a symmetric matrix. Instead of a symmetric model we use the weighted ...
2
votes
3answers
249 views

eigenvalue of Laplacian matrix

If we have a Laplacian matrix $\boldsymbol{A}$ such that \begin{align} &A_{ii} >0 \\ &A_{ii}=-\sum_{j\neq i}A_{ij} \end{align} with known eigenvalues $\lambda_i$. Define the matrix ...
3
votes
0answers
220 views

A problem on graph theory and complex numbers!

Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that $$ ||z_1||=\ldots = ...
1
vote
0answers
114 views

“Stable” bounds on maximum size independent set in a graph

Suppose we have a graph $G=(V,E)$, and we want to upper bound $|I|/|V|$, where $I$ is the largest independent set in $G$. Then there is the Hoffman bound, which is $|I|/|V| \leq ...
1
vote
0answers
63 views

Second eigenvalue of a weighted tree

Hello, I am interested in upper bounding the second largest eigenvalue of the adjacency matrix of a graph $T$ with the following property: 1. $T$ contains self loops. 2. $T$ contains multiple edges ...
4
votes
1answer
206 views

What is the largest possible operator norm of a sparse (0,1)-matrix?

Inspired by this question, I was wondering about the following problem: Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does ...
-1
votes
1answer
205 views

Upper bound on iterations count for power iteration algorithm

I'm stuck trying to get upper bound on iterations count for power iteration algroithm for finding first eigenvalue of adjacency matrix $A$ given tolerance value. I've tried to figure something out ...
2
votes
0answers
108 views

Optimization over Spectral Laplacian in cycles and trees

Is there any idea on how one can deal with an optimization problem of sum of k largest eigenvalues(min) of Laplacian matrix of a simple cycle or tree? I would like to use semidefinite programming for ...
4
votes
1answer
484 views

How many distinct eigenvalues does a random graph have?

It is well-known that a random graph a.e. has diameter 2. It is also well-known that the number of distinct eigenvalues of a graph is at least the diameter plus one. But what is known about the ...
0
votes
0answers
87 views

Global solution for spectral clustering

I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...
1
vote
2answers
233 views

How to identify bridge nodes between nearly connected graph components in partitioned adjacency matrices?

I have adjacency matrices which have nearly connected components. That is partitions with a dense number of edges between nodes in the same group and few edges acting as bridges between these groups. ...
0
votes
1answer
290 views

Find edge weights that fit given node weights

Let $G = (V,E)$ be a connected simple graph (unweighted, undirected, no selfloops) on $n$ nodes. Let $\mathbf{d} := (d_1, d_2, ..., d_n) \in \mathbb{R}_{>0}^n$ be a vector of arbitrary given node ...
1
vote
0answers
117 views

Kernel of modified Kronecker sum

The Kronecker sum of two matrices $A \in M(n \times n, \mathbb{R})$ and $B \in M(m \times m,\mathbb{R})$ is defined by the matrix $$A \oplus B = A \otimes I_m + I_n \otimes B \in M(nm \times nm, ...
2
votes
3answers
333 views

1 or -1 as an eigenvalue of graph

I have a regular and arc transitive graph which I think that either 1 or -1 is an eigenvalues of adjacency matrix of this graph. How can I prove it? Is there any classification of graphs which have 1 ...
1
vote
1answer
99 views

Optimal weights for large eigenvalues of Laplacian

For a weighted and directed graph $G$ on $n$ vertices we define the Laplacian matrix by $L(G) = D(G)-A(G)$. Here $(i,j)$-th entry of ${A(G)}$ equals the weight $w_{ij}$ of the edge from $i$ to $j$ if ...
1
vote
1answer
138 views

a variation on the theory of equitable partitions for graphs

Assume you have a graph with an equitable partition with respect to cells $V_1,\ldots,V_n$. Accordingly, you can take the cellwise average value of a function on the node set - in other words, the ...
8
votes
3answers
695 views

Eigenvalues of a special block matrix associated with strongly connected graph

Definition Let $G=(V,E,A)$ be a strongly connected directed graph, where $V=\{1,2,...,n\}$ denotes the vertex set, $E$ is the edge set, and $A$ is the associated adjacency matrix with $0-1$ ...
9
votes
2answers
370 views

When Do a Few Eigenvectors of Graph Laplacians Not Determine the Graph?

Essentially as the title, but I'll give a little bit more background. I have some finite graph $G$ with $n$ vertices and adjacency matrix $A$. Let $D$ be the $n$ by $n$ matrix with the degree of ...
5
votes
1answer
451 views

Complexity of finding a 0-1 vector in a subspace or showing that there is none

This question, is a slightly different disguise (see below), came up in discussions of this question about equitable partitions A $0,1$ vector in $\mathbb{Z}^n$ is any vector with all entries $0$ and ...
2
votes
0answers
239 views

Matrix Operations Preserving Hurwitz Stability

I begin with terminology I use in the question. A real square matrix $A$ is negative-stable if for every eigenvalue $\lambda$ of $A$, ${\mathrm{Re}}(\lambda) < 0$; $\ast$-negative-stable ...
1
vote
1answer
546 views

equitable partitions

It is well known that if $\pi$ is an equitable partition of a graph, then the spectrum of the corresponding partition matrix is a subset of the spectrum of the graph's matrix (where the matrix can be ...
2
votes
2answers
504 views

Positive semidefinite decomposition, Laplacian eigenvalues, and the oriented incidence matrix

Suppose $A\in\mathbb{C}^{n\times n}$ is Hermitian and positive semidefinite with some decomposition $A=BB^*$, where $B=(b_{ij})\in\mathbb{C}^{n\times m}$ (not necessarily the Cholesky decomposition). ...
2
votes
2answers
232 views

Ax=0, estimate min(Hamming(x)) ? Equivalently: Bipartite graph. How to find (estimate) minimal number of vertices1 which are connected with EVEN number of vertices2 ? Equivalently: estimate minimal weight of error correcting code ?

Consider system of linear equations Ax=0 over $F_2$ (field with two elements {0,1}). Where number of variables is bigger than equations - so we have many solutions $x$. Question How to estimate ...
2
votes
2answers
573 views

Computing the multiplicity of an eigenvalue of a 0-1 symmetric matrix…

When we want to compute the multiplicity of an eigenvalue of a 0-1 symmetric matrix (viewed as the adjacency matrix of an undirected regular graph), we commonly resort to the know lemma of Feit and ...
3
votes
3answers
475 views

Is this statement about the real edge space of a graph known or trivial?

The statement is: ($u$ is a fixed node in a fixed graph $G$) $G$ is 3-connected if and only if the set of u-cycles span $\mathbb{R}^{E(G)}$. A u-cycle is a simple (no vertex repetitions) cycle in G ...
7
votes
3answers
469 views

Relationship between free probability and deterministic graphs?

Consider the $N\times N$ matrix $$ M = \left(\begin{array} \\ 0 & 1 & & 0 \\ 1 & \ddots & \ddots & \\ & \ddots & \ddots & 1 \\ 0 & & 1 & 0 \\ ...
3
votes
2answers
689 views

Complex Eigenvalues of Directed Graphs

I have been computing eigenvalues of adjacency matrices for several directed (not necessarily strongly connected) graphs and one remarkable property seemed to hold (each graph that I have examined ...
1
vote
1answer
266 views

Encoding information about submatrix determinants

$M$ is an $n\times n$ matrix. Consider the submatrices $M(P;Q)$ formed from $P$ rows and $Q$ columns of $M$ where $P$ and $Q$ are disjoint indices. Is there some way to encode the various ...
1
vote
2answers
775 views

Laplacian spectrum for product graphs

Let $G$ and $H$ be simple graphs. I am interested in the Laplacian spectrum for various products of $G$ and $H$ namely the cartesian product, tensor product, lexicographical product and strong ...
2
votes
1answer
167 views

Planar Graphs and Skew Binary Spaces

Let $G$ be a planar triangulation on $3m$ edges and $m+2$ vertices. Let $A$ be the binary matrix obtained from the incidence matrix of $G$ by deleting a row (equivalently we require the rows of $A$ to ...
4
votes
3answers
589 views

Spectral radius of a proper subgraph

I came across a Chinese reference in the paper "On the spectral radius of trees with fixed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of ...
27
votes
3answers
2k views

How much linear algebra can be done with graphs?

Let G be a finite directed acyclic graph, with sources $A=\{a_1,\ldots,a_n\}$ and sinks $B=\{b_1,\ldots,b_n\}$, with edge weights $w_{ij}$. The weight of a directed path P is the product of weights of ...
1
vote
3answers
686 views

Defining a canonical ordering of matrix rows/columns [closed]

I would like to find a way to define a canonical ordering of rows/columns in a matrix. If two rows/columns cannot be ordered according to this canonical ordering (i.e. they're the "same"), then it ...
2
votes
0answers
237 views

When is polytope compatible with network flow?

A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
1
vote
1answer
820 views

Can a complex non-skew Hermitian matrix have purely imaginary eigenvalues?

I am trying to determine if a certain matrix can have purely imaginary eigenvalues. My question in its most general form is weather a complex matrix that is not skew-Hermitian and irreducible can ...
2
votes
1answer
215 views

Singular values of differences of square matrices

Suppose $A, B \in \mathbb{R}^{n \times n}$. Let $\sigma_1(A),\ldots,\sigma_n(A)$ be the singular values of $A$, and let $\sigma_1(B),\ldots,\sigma_n(B)$ be the singular values of $B$. If I know these ...
0
votes
3answers
306 views

Morphisms between representations

I am looking at the automorphism group $G$ of a graph, represented as permutation matrices. The point in a proof I am trying to understand goes something like this: "For any permutation matrix $P$ ...
2
votes
2answers
597 views

eigenvalues of edge regular graphs

In graph theory, an edge regular graph is defined as follows. Let G = (V,E) be a regular graph with v vertices and degree k. G is said to be edge regular if there is also integer λ such that: Every ...