# Tagged Questions

**1**

vote

**1**answer

73 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

**0**answers

74 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

**1**answer

98 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

**1**answer

145 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

**1**answer

169 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

**1**answer

161 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

**0**answers

181 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

**0**answers

59 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

**1**answer

155 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

**3**answers

229 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

**0**answers

207 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

**0**answers

84 views

### Excluding linear size independent sets in graphs

What are some known criteria of excluding large independent sets (linear size) in k-regular graphs?
I know one criterion is that the smallest eigenvalue of the adjacency matrix shouldn't be too small ...

**1**

vote

**0**answers

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

**1**answer

188 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

**1**answer

190 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 ...

**1**

vote

**0**answers

105 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

**1**answer

459 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

**0**answers

85 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

**2**answers

206 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

**1**answer

251 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

**0**answers

107 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

**3**answers

323 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

**1**answer

95 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

**1**answer

135 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

**3**answers

690 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

**2**answers

352 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

**1**answer

402 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

**0**answers

211 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

**1**answer

491 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

**2**answers

482 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

**2**answers

222 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

**2**answers

566 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

**3**answers

471 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

**3**answers

455 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

**2**answers

665 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

**1**answer

261 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

**2**answers

725 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

**1**answer

166 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

**3**answers

547 views

### Spectral radius of a proper subgraph

I came across a Chinese reference in the paper "On the spectral radius of trees with ﬁxed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of ...

**27**

votes

**3**answers

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 ...

**0**

votes

**3**answers

619 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

**0**answers

228 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

**1**answer

807 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

**1**answer

211 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

**3**answers

305 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

**2**answers

587 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 ...

**10**

votes

**0**answers

271 views

### Matroids with prescribed independent sets

Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...

**11**

votes

**2**answers

937 views

### Combinatorial proof of (a special case of) the spectral theorem?

The spectral theorem for a real $n \times n$ symmetric matrix $A$ says that $A$ is diagonalizable with all eigenvalues real. If $A$ happens to have non-negative integer entries, it can be interpreted ...

**15**

votes

**5**answers

1k views

### The middle eigenvalues of an undirected graph

Let $ \lambda_1 \ge \lambda_2 \ge \dots \lambda_{2n} $
be the collection of eigenvalues of an adjacency matrix of an undirected graph $G$ on $2n$ vertices. I am looking for any work or references ...

**22**

votes

**15**answers

6k views

### Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...