# Tagged Questions

74 views

85 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 ...
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 ...
190 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 ...
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 ...
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 ...
460 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 ...
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 ...
207 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. ...
257 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 ...
110 views

669 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 ...
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 ...
734 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 ...
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 ...
548 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 ...
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 ...
623 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 ...
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 ...
809 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 ...
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 ...
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$ ...
588 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 ...
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 ...
938 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 ...
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 ...