All Questions
Tagged with matrices graph-theory
102 questions
34
votes
1
answer
789
views
Which graphs on $n$ vertices have the largest determinant?
This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc.
The determinant of ...
- 12.7k
30
votes
4
answers
4k
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 ...
- 25.5k
28
votes
3
answers
2k
views
Is every positive integer the permanent of some 0-1 matrix?
In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:
Is it true that for every positive integer $k$ there exists a balanced ...
- 82.6k
21
votes
5
answers
2k
views
The middle eigenvalues of an undirected graph
Let $ \lambda_1 \ge \lambda_2 \ge \dots \ge \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 ...
- 784
13
votes
0
answers
237
views
A Dynkin type classification result in linear algebra
Let $G$ be a finite directed acyclic graph. The Cartan matrix $C_G=C$ of $G$ is defined as the matrix with rows and colums indexed by the vertices of $G$ and $c_{i,j}$ counts the number of paths from $...
- 26.5k
12
votes
2
answers
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 ...
- 13.1k
11
votes
5
answers
2k
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,699
11
votes
1
answer
467
views
Correspondence between matrix multiplication and a graph operation of Lovász
In his book "Large networks and graph limits", Lovász describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a ...
- 2,339
11
votes
1
answer
558
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,388
10
votes
2
answers
2k
views
When are the adjacency matrices of non-isomorphic graphs similar?
From Wikipedia.
In linear algebra, two n-by-n matrices A and B are called similar if
$$ B = P^{-1} A P$$
for some invertible n-by-n matrix $P$.
If $P$ is a permutation matrix, $A$ and $B$ are ...
- 25.4k
8
votes
3
answers
8k
views
Spectrum of an adjacency matrix
The adjacency matrix of a non-oriented connected graph is symmetric, hence its spectrum is real.
If the graph is bipartite, then the spectrum of its adjacency matrix is symmetric about 0. A few ...
- 3,388
8
votes
2
answers
377
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 ...
- 985
7
votes
1
answer
337
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, \dots, ...
- 151k
7
votes
2
answers
462
views
Large power of an adjacency matrix [closed]
The adjacency matrix I have at the start is
[0,1,0,0,0]
[0,0,1,0,0]
[1,0,0,1,1]
[0,0,0,0,0]
[0,0,0,0,0]
I don't understand why this matrix^9999 equals
[1,0,0,1,1]
[0,1,0,0,0]
[0,0,1,0,0]
[0,0,0,0,...
7
votes
1
answer
641
views
Lower bound on the eigenvalues of the Laplacian
I am looking for a graph for which $2 d_{i} < \mu_{i}$, for some index $i$, where $\mu_{1} \leq \mu_{2} \leq \dots\leq \mu_{n}$ are the eigenvalues of the Laplacian matrix $L(G)$ and $d_{1} \leq d_{...
- 123
7
votes
1
answer
386
views
Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?
Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent:
The all-one vector $j$ is contained in the conic hull of $col(A)$.
...
- 81
7
votes
0
answers
177
views
Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?
Let $A$ be a $2n$-by-$2n$ matrix with entries in
$\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal
matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$
has rank $\...
- 20.2k
7
votes
0
answers
335
views
Does this inequality always hold?
Denote the adjacency matrix of a given undirected graph by $g$. It is an $n$-by-$n$ symmetric Boolean matrix with elements on the diagonal to be zero ($n\geq 3$). Let $g_{12}=g_{21}=g_{13}=g_{31}=1$ ...
- 79
6
votes
1
answer
515
views
Non-diagonalizability of the adjacency matrix of a directed graph
Let $G$ be a directed graph with no multiple edges or loops and let $P_i$ be its vertices. Let $A$ be the corresponding adjacency matrix of $G$, i.e. $a_{i,j}=1$ if and only if there is a directed ...
- 4,058
6
votes
3
answers
251
views
How many $40$-vertex cubic bipartite graphs have determinant $\pm 3$?
To get some feel for the size of a particular computation, I would like to know the approximate number of (pairwise-nonisomorphic) cubic bipartite graphs on $40$ vertices whose bipartite adjacency ...
- 12.7k
6
votes
1
answer
1k
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 \...
- 11.4k
6
votes
1
answer
726
views
Combinatorics and symmetry in matrices under row and column swaps
Suppose we have a $m\times n$ matrix and a sequence of numbers with which to fill the matrix, $\{c_1,c_2 \dots c_k \}$. I like to think of the numbers as colors, hence the notation. How many unique ...
6
votes
0
answers
940
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 ...
- 61
5
votes
1
answer
706
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 ...
- 7,633
5
votes
1
answer
425
views
Determining the primitive order of a binary matrix
Let ${\bf A}_n$ be an $2n \times 2n$ matrix that is defined as follows
$$
{\bf A}_n=\left(
\begin{array}{c}
0&0&\cdots&0&0&0&0&1&1\\
0&0&\cdots&0&0&...
- 313
5
votes
1
answer
382
views
Is it possible to compute a valid Laplacian matrix from an effective resistance matrix?
I am wondering whether it is possible to retrieve a node-admittance matrix $G$ (also called Laplacian matrix) in a purely resistive network composed of nets $\{1, \dots, i, \dots, j, \dots, n\}$, from ...
4
votes
2
answers
600
views
Co-trees of a simple graph
Consider fundamental cycles (say $k$ of them) of a specific spanning tree of a simple graph (with $m$ edges) which is also connected and has no one-edge bonds.
Make the graph directed (in an arbitrary ...
- 419
4
votes
1
answer
140
views
Counting adjacency matrices
Here is a question that has come up in the context of a problem that involves counting partially ordered sets.
For an adjacency matrix $A$, let $p$ be the sum of elements in the strict upper ...
- 192
4
votes
1
answer
420
views
Visualizing the elements of a finite group and does the Gram matrix determine the finite group?
Let $G$ be a finite group with $n = |G|$ elements. By Cayley's theorem for finite groups, we have an injective homomorphism of groups:
$$
\pi : G \rightarrow S_n, \quad g \mapsto \pi(g)
$$
where ...
- 3,054
4
votes
2
answers
1k
views
What's the full assumption for Laplacian matrix $L=BB^T=\Delta-A$?
Graph with no-selfloop, no-multi-edges, unweighted.
directed
For directed graph Adjacency matrix is a non-symmetric matrix $A_{in}$ considering indegree or $A_{out}$ considering outdegree. Degree ...
- 211
4
votes
0
answers
59
views
Graph-class defined by matrix-like vertex-operations
Let $m$ be a positive integer. We define a (directed) graph on $m(m-1)$ vertices
$$V = \bigl\{(i,j) \mid i \ne j,\, i,j\in\{1,\dots,m\}\bigr\}$$
and edges as follows:
$(i,j) \in V$ is adjacent (...
- 577
4
votes
0
answers
149
views
Zero diagonal nonsymmetric block checkerboard matrix: orbits and numerical ranges
Let $A \in \mathbb{R}^{m \times m}$ be a nonsymmetric zero diagonal matrix with a zero/non-zero pattern which is symmetric and persymmetric (i.e. symmetric in the northeast-to-southwest diagonal).
If ...
- 323
4
votes
0
answers
657
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$ ...
- 41
4
votes
0
answers
434
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$. ...
- 51
4
votes
0
answers
351
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 ...
- 13.5k
3
votes
2
answers
316
views
Relation graph isomorphism to discrete logarithm
$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.
Q1 ...
- 25.4k
3
votes
1
answer
102
views
matching two positive-semidefinite matrices
Let $M_1$ and $M_2$ be two real positive-semidefinite matrices. Is there any algorithm to compute a permutation matrix $P$ to minimize $\| M_1-PM_2P^T \|_F^2$ or equivalently to maximize $trace(...
- 193
3
votes
1
answer
166
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,962
3
votes
1
answer
336
views
Eigenvalues of random graphs
At time $t=0$, let $G_n(V,E)$ be a graph with $n$ vertices and $m < n$ edges. Then there exists a unique symmetric adjacency matrix $A_n$ associated with $G_n(V,E)$, defined as follows: $a_{ij} = 1$...
- 101
3
votes
2
answers
197
views
Proper Latin sub-squares of generalized Latin squares
Say we have a generalization of a Latin square, where the square is of size $n \times n$, $n = ab$ and each row and each column has $b$ occurrences of each of $[1, \dots, a]$. Is there always ...
- 31
3
votes
0
answers
108
views
Positive vector in the kernel of an skew-symmetric incidence matrix
Let $G=(V,A)$ be an oriented graph, stronlgy connected with $n\in\mathbb{N}^*$ vertices. Let $M\in\mathcal{M}_n(\mathbb{R})=(m_{i,j})$ be an skew-symmetric matrix of size $n$ and rank $r$, such that ...
- 449
3
votes
0
answers
82
views
Maximum number of negative entries in a matrix with positive diagonal and given rank
Suppose $A \in \mathbb{R}^{n \times n}$ has positive entries on it main diagonal and $\mbox{rank}(A) =: d < n$. Then, what is the maximum number of many negative entries $A$ can contain?
If, in ...
- 31
3
votes
0
answers
350
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 ...
3
votes
0
answers
1k
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 if for ...
- 105
2
votes
2
answers
330
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A ...
- 25.4k
2
votes
1
answer
316
views
When does a row standardized adjacency matrix have a real spectrum?
A colleague in spatial statistics was looking at a map with about 600 regions. For the application she's considering, the induced adjacency matrix had some undesirable properties (where two regions ...
- 6,001
2
votes
2
answers
461
views
On Knot Equivalence problem statement
How is the knot equivalence problem represented?
By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with ...
- 13.9k
2
votes
2
answers
424
views
A certain matrix associated to graphs
I am not very familiar with graph theory, but I need some results for my work. Thus, the question is, whether the following has already been studied and where I can find it. Let $G=(V,E)$ be an graph ...
- 408
2
votes
5
answers
5k
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 ...
2
votes
2
answers
819
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 ...
