1
vote
0answers
11 views

How to restructure adjacency matrix $A$ from shortest distance matrix $B$ in Network topology inference

An undirected graph with $n$ nodes could be referred to as an adjacency matrix $A$. $A=[a_{ij}]_{n×n}$ with $a_{ij}=a_{ji}=1$ standing for there being an edge between node $i$ and node $j$, and no ...
0
votes
0answers
97 views

Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$

Valiant shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$ to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$ for certain efficiently computable $t(F)$ and matrix ...
10
votes
1answer
267 views

doubly-stochastic isomorphisms of graphs

A doubly stochastic matrix that commutes with the adjacency matrix of a graph is a doubly-stochastic automorphism of that graph (definition by Tinhofer 1986). Each (classical) automorphism of a graph ...
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 ...
6
votes
1answer
149 views

A family of skew-symmetric matrices corresponding to cycles in graphs

When investigating loops in Markov chains I ran into the following observation. A cycle in a graph $G$ with $n$ vertices may be represented by a matrix $\Gamma \in \mathbb R^{n \times n}$ having the ...
3
votes
2answers
297 views

Which directed graphs have a normal adjacency matrix?

I am working on a problem in matrix analysis and I am looking for certain types of normal matrices. I suspect that these "special" normal matrices arise as adjacency matrices of certain graphs. My ...
3
votes
0answers
182 views

Beating Kadane's Algorithm

I am seeking some reference on already existing work for the following problem. Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
4
votes
1answer
210 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
215 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 ...
3
votes
0answers
537 views

determinant of fibonacci-sum graphs

We have a simple graph with vertices $\{v_1, v_2, ... v_n\}$. The adjacency matrix of this graph is $A= (a_{ij})$ so that $a_{ij}=1$ if $i+j$ belongs to the Fibonacci sequence; $a_{ij}=0$ ...
0
votes
1answer
136 views

two non-degenerate quadratic forms on $GF(2)^2r$

I know this: There are two non-degenerate quadratic forms on $GF(2)^2r$. The hyperbolic form may be taken to be $Q^+(x)=x_0 x_1 + \cdots +x_{2r-2}x_{2r-1}$ , and the elliptic form to be ...
5
votes
1answer
362 views

Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

This question is motivated by a talk I went to earlier today. Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$. Let $$\lambda_1\geq \lambda_2 \geq\dots \geq ...
2
votes
0answers
258 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 ...
2
votes
2answers
521 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
237 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 ...
6
votes
1answer
283 views

Maximal disarrangement of $n \times n$ numbers

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin: the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, ...
2
votes
2answers
577 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 ...
4
votes
0answers
411 views

Smallest matrix covered by many random n by n matrices

We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...
24
votes
4answers
2k views

Adjacency matrices of graphs

Motivated by the apparent lack of possible classification of integer matrices up to conjugation (see here) and by a question about possible complete graph invariants (see here), let me ask the ...
3
votes
1answer
229 views

Finding a 5-cycle in a sparse graph efficiently.

Hi, I was reading this thread: Finding a cycle of fixed length I want to find a 5-cycle in a graph. Actually, what I really want is a shortest odd cycle of length at least 5, but maybe that is a ...
6
votes
0answers
612 views

inverse eigenvalue problem on graph laplacian

I am trying to construct a graph Laplacian matrix from a set of eigenvalue. I've read several papers about inverse eigenvalue problems but to be honest I didn't understand clearly. Could somebody ...
1
vote
5answers
2k views

Nodes clusters with a distance matrix

Hi, I have a (symmetric) matrix $M$ that represents the distance between each pair of nodes. For example, A B C D E F G H I J K L A 0 20 20 20 40 60 60 60 100 120 ...
11
votes
2answers
2k views

Integral positive definite quadratic forms and graphs

Let me start with a question for which I know the answer. Consider a symmetric integral $n\times n$ matrix $A=(a_{ij})$ such that $a_{ii}=2$, and for $i\ne j$ one has $a_{ij}=0$ or $-1$. One can ...
3
votes
0answers
307 views

Combinatorics of signed oriented graphs/skew-symmetric matrices

Consider a "complete" signed graph on $n$ vertices indexed by $1,2,\dots,n$, that is, a graph in which any two distinct vertices $i$ and $j$ are connected by an oriented edge. For each pair of ...
1
vote
5answers
1k views

Properties of Graphs with an eigenvalue of -1 (adjacency matrix)?

I am wondering if there are special classes of graphs that have eigenvalue of -1 for the adjacency matrix. I know that the complete graphs, Kn, have this property, but am wondering if other graphs do ...