All Questions
Tagged with linear-algebra graph-theory
180 questions
3
votes
1
answer
200
views
Matrix-tree theorem for inverse matrices
Let $L$ be the Laplacian of a directed weighted graph on $n$ nodes, e.g., for $n=4$:
$$
L = \left(\begin{array}{cccc} w_{1,1}+w_{1,2}+w_{1,3}+w_{1,4} & -w_{1,2} & -w_{1,3} & -w_{1,4}\\ ...
- 20.2k
0
votes
0
answers
15
views
Change in two spectral deviations due to edge deletion in a signed graph
Prove (or disprove) the following. Let $\Sigma=(G,\sigma)$ be a given signed graph. If $\lambda_1\ge\lambda_2\ge\cdots\ge \lambda_n$ and $\mu_1\ge\mu_2\ge\cdots \ge \mu_n$ are the eigenvalues of the ...
- 61
4
votes
1
answer
103
views
When do the nonzero eigenvalues of a directed graph Laplacian have the same absolute value?
Question: Let $G$ be a strongly connected directed graph on $n$ vertices with Laplacian $L(G)$. Then $L(G)$ has one zero eigenvalue $\lambda_1=0$ and $n-1$ nonzero eigenvalues $\lambda_2,\ldots,\...
- 145
0
votes
0
answers
70
views
Cyclotomic eigenvalue question for Distance-regular graph
I have read this paper. So, I am just thinking about if the following guess is true:
GUESS: Any Distance-regular graph (DRG) has cyclotomic character value property (which means the eigenvalues of a ...
- 109
1
vote
1
answer
133
views
Graceful labeling of the complete bipartite graph and its laplacian quadratic form diagonalized
A graceful labeling of a connected simple undirected graph $G=(V,E)$ is a map $f:V\to\lbrace 1,...,|E|+1\rbrace$ such that for all $t\in\lbrace 1,...,|E|\rbrace$ there is a (trivially unique) $\langle ...
- 91
24
votes
3
answers
866
views
Mark some vectors in $\mathbb{R}^n$ in a way that every orthonormal basis has an odd number of marked vectors
Let $n$ be a natural number. Is there a set $S$ of vectors of norm $1$ in $\mathbb{R}^n$ such that every orthonormal basis of $\mathbb{R}^n$ contains an odd number of vectors from $S$?
If $n$ is odd, ...
- 679
0
votes
1
answer
131
views
Function of eigenvalues of Laplacian matrix
Let $G$ be a simple $n$-vertex graph and let $\mu_n\geq\mu_{n-1}\geq\dots\geq\mu_1$ be the eigenvalues of its Laplacian matrix, how can I find a function $$f(\mu_1,\mu_2,\dots\mu_n) \text{ such that } ...
- 53
0
votes
0
answers
36
views
A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial
We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle.
Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...
- 4,058
5
votes
0
answers
137
views
Given a collection of vectors $x_1,\ldots,x_k$, which inner products $\langle x_i,x_j\rangle$ are needed to uniquely determine all inner products
Given a collection of vectors $x_1,\ldots,x_k$, which inner products $\langle x_i,x_j\rangle$ need to be known to uniquely determine all inner products? I'll begin with the specific case I am ...
- 351
1
vote
0
answers
255
views
Interpreting positive semidefinite matrix as a graph
Given any symmetric matrix $S \in \mathbb{R}^{n \times n}$, if $S \succeq 0$, is there a way to encode $S$ into a graph such that it takes into account the positive semidefinite constraint, and ...
- 275
4
votes
0
answers
1k
views
Number of arrangements that contain at least 1 path from top to bottom of 2D matrix
I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white.
With that information, I can easily calculate the total number of black element arrangements that exist ...
- 47
3
votes
1
answer
148
views
Spectrum of the adjacency matrix of certain directed graphs
For an undirected graph $G$, its adjacency matrix $A_G$ is symmetric, and by the (consequence of) spectral theorem, each of its Jordan blocks has size $1$. This is not true for a general directed ...
- 161
2
votes
1
answer
133
views
Is the sum of the circulant matrix with a super upper triangular matrix diagonalizable?
By the circulant matrix $C$ in $M_n(\mathbb{R})$, we mean that
$$C=[e_n|e_1|\cdots|e_{n-1}]$$ where $e_1,\cdots,e_n$ are the standard basis vectors in $\mathbb{R}^n$. It is well-known that
$$C=\...
- 4,058
1
vote
1
answer
198
views
Directed graph whose adjacency matrix admits only 0 as eigenvalue
Let $G$ be a directed graph 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 edge from $P_i$
to $P_j$, ($a_{i,...
- 4,058
6
votes
1
answer
518
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
3
votes
0
answers
259
views
Efficient way to calculate Smith Normal Form of large integer matrices
I am interested in calculating the Smith Normal Form for Laplacian matrices of hypercube graphs. Using the elementary divisors method from SAGE, I was able calculate up to the 11-cube (which has a $2^{...
3
votes
2
answers
176
views
Lower bound on the rank of a graph
[This has been edited in response to comments from Fedor Petrov]
Suppose that $n=dm$ with $d,m>1$. Consider an $n\times n$ matrix $M$ such that
All diagonal entries are equal to one
Each row has $...
- 56.9k
0
votes
0
answers
126
views
On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph
Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
- 61
5
votes
2
answers
550
views
Adjacency matrix of tournament
I met a question in Bondy and Murty’s Graph theory (§1.5.13)
The adjacency matrix of a digraph $D$ is the $n \times n$ matrix $\mathbf{A}_D = (a_{uv})$, where $a_{uv}$ is the number of arcs in $D$ ...
- 51
2
votes
1
answer
407
views
A property of directed acyclic graph
Suppose $A \in \mathbb{R}^p$ is the adjacency matrix of a weighted directed acyclic graph $D$ with vertex set $\left\{v_{1}, v_{2}, \ldots, v_{p}\right\}$, i.e.
$$
a_{i j}=\left\{\begin{array}{lr}
...
0
votes
0
answers
56
views
Determining the total number of nonzero expansion terms in a (0,1)-matrix
Let $A=(a_{ij})_{n\times n}$ be a $(0,1)$-matrix such that it contains equal number of $1$s in each row and column. Is there any general method to count the total number of the nonzero terms $\prod_{i=...
- 133
7
votes
2
answers
1k
views
Why is the spectrum of Erdős–Renyi random graph approximately symmetric?
I am recently self-learning random matrix theory and made some simulations about the spectrum of Erdős–Renyi random graph $G(n,p)$ when $np\to\infty$,
and $np\to c=2,3$.
The plots above are already ...
- 715
2
votes
0
answers
89
views
Odd $k$-cycle counts in graph with adjacency matrix $A$ is leading term in $\operatorname{tr} A^k$?
In a recent paper of Neeman, Radin, and Sadun, Moderate Deviations in Cycle Count, in the first line of section 7.3 they wrote $\tau_k(A)=\frac{\operatorname{tr}A^k}{n^k}+O(\frac 1n)$, but I don't ...
- 715
11
votes
0
answers
541
views
How to determine the sign for the sum over all simple paths in the graph
$\DeclareMathOperator\perm{perm}\DeclareMathOperator\len{len}$Let $A$ be the adjacency matrix of a tree $T$ for some ordering $v_1,...,v_n$ of the vertices, and let $D=xI-A$ its characteristic ...
- 1,362
9
votes
0
answers
378
views
How many orthogonal matrices (not orthonormal) are there with entries in $\{0,1,−1\}$?
Here by orthogonal matrix I mean just the rows are mutually orthogonal. Two such matrices are equivalent if one can be obtained from the other by permutations of rows and columns, or change of signs ...
- 745
2
votes
0
answers
72
views
How to delete the maximum number of rows of a Boolean matrix by maintaining the sum greater than zero in each column
I have a Boolean matrix (entries are "0" or "1"), which is not square. The sum over each row and each column is constant (but they can be two different values). I would like to ...
- 21
2
votes
1
answer
521
views
Solution to the sum of k-step path lengths between node pairs in directed weighted graphs
In a non weighted graph, the adjacency matrix ($A$) raised to the power $k$ will return the number of k-step paths between nodes $i$ and $j$ at the entry $a_{ij}$. Is there an equivalent for weighted ...
- 23
2
votes
1
answer
251
views
Dimension of circuit space of a matroid
If $G$ is a graph with edge set $E$, let $W$ be the $\mathbb{Z}/2$-vector space generated by the elements of $E$. If $A = \{a_1, \dots, a_n\} \subset E$, let $\bar{A} = a_1 + \dots + a_n \in V$; then $...
- 95
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
1
vote
0
answers
140
views
Adjacency matrix/tensor operations for graph sequences?
Consider a graph $G=(V,E)$. Its adjacency matrix $A$ is defined by $A_{u,v} = 1$ if $(u,v)\in E$, $0$ otherwise.
Consider a vector $x$ that associates a value $x_v$ to each vertex of $G$. Consider the ...
- 1,444
6
votes
1
answer
746
views
Relationship between spectral gaps of adjacency and Laplacian matrices of graphs
Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).
Let $A$ be ...
- 150
3
votes
0
answers
181
views
A conceptual explanation for the Kirchoff matrix theorem in terms of the quiver algebra
On the wikipedia page for the Kirchoff matrix theorem, they state a souped up version of the theorem:
Let $G$ be a finite undirected loopless graph and let us form the square matrix $L$ indexed by the ...
- 7,746
6
votes
1
answer
312
views
Determinant of walk matrix for a skew-symmetric matrix of even order
Let $S=(s_{ij})$ be a skew-symmetric integral matrix of order $n$. We only consider the case that $n$ is even. Let $e$ be the all-one vector in $\mathbb{R}^n$. Define the walk matrix $$W(S)=[e,Se,\...
- 437
1
vote
0
answers
127
views
Delocalization of eigenvectors of graph Laplacians
Let $(V,E)$ be an undirected, connected graph with $n$ nodes. The graph Laplacian is defined as $L = D - A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_1 < \...
- 41
0
votes
0
answers
425
views
Linear independence of vectors in Graph Theory
I have poste this question on StackExchange but there were no takers - would I be luckier on this site?
Most of this is well known, so let me just restate the corresponding Math:
Given a connected, ...
- 419
-1
votes
1
answer
65
views
A follow-up question in a proof in a paper on complete multipartite graphs
A follow-up question from the following article/paper:
"Proof of a conjecture on distance energy change of complete multipartite graph due to edge deletion"
by Shaowei Sun and Kinkar Chandra ...
- 199
3
votes
1
answer
137
views
A question about a proof in a paper on complete multipartite graphs
I was recently reading the following article/paper:
"Proof of a conjecture on distance energy change of complete multipartite graph due to edge deletion"
by Shaowei Sun and Kinkar Chandra ...
- 199
3
votes
1
answer
374
views
Convergence on iterating a piecewise function
Given the four functions $P_1$, $P_2$, $N_1$ and $N_2$ (which together is a piecewise function) each with domain and range as shown above:
Is there an explanation as to why starting at any integer (...
- 143
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
9
votes
3
answers
729
views
Math history research: a copy of "Zur relativen Wertbemessung der Turnierresultate" , eigenvector centrality by Edmund Landau
I'm searching for a copy of an old paper made by Edmund Landau:
Zur relativen Wertbemessung der Turnierresultate, Deutsches Wochenschach, 11. Jahrgang (1895), 366–369.
However, I can't find it ...
- 93
2
votes
0
answers
79
views
Upper bound for smallest eigenvalue of infinite family of graphs
Let $\left\{G_{n}\right\}_{n=1}^{\infty}$ be a sequence of regular simple connected graphs with at least one edge such that $G_i$ is an induced sub-graph of $G_{i+1}$ and is not equal to $G_{i+1}$.
...
- 133
3
votes
1
answer
268
views
How to prove that for the real stable characteristic polynomial $P=\Phi_T$ of a tree $T$, $P_iP_j-PP_{ij}=(\Phi_{T-[v_i,v_j]})^2$?
If $G$ is a labeled graph, the multi-affine characteristic polynomial (which depends on labeling) is defined by
$\Phi_G(x_1,...,x_n)=\det(I_x-A)$, where $I_x$ is the diagonal matrix $diag\{x_1,...,x_n\...
- 487
7
votes
1
answer
463
views
Boundedness of total current in electrical network
Consider the following symmetric matrix (adjacency matrix):
$$A=(a_{ij})_{1\leq i,j\leq n}$$
such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...
- 1,495
11
votes
2
answers
353
views
Exponential decay of voltage potential difference
Consider the following adjacency matrix of a complete graph:
$$A=(e^{-|i-j|})_{1\leq i\neq j\leq n}$$
with 0 on the diagonal. Let $D=diag\{d_1,...,d_n\}$ be the degree matrix where $d_i=\sum_{j\neq i}...
- 1,495
3
votes
1
answer
237
views
Mac Lane's planarity criterion and 2-bases
Mac Lane's planarity criterion states that a graph is planar if and only if its cycle space has a basis such that each edge is contained in at most two cycles. We call a basis with this property a 2-...
- 105
1
vote
0
answers
53
views
Upperbound on Shannon capacity of graph and strong product of graph
Given a Graph $G = (V=[n],E)$, if a symmetric matrix $B$ fits $G$, it has non-zero diagonal elements and 0 on off-diagonal entries if $\{i,j\}$ are non-edge in $G$.
Let \begin{equation}
R(G) = \min ...
- 33
2
votes
0
answers
288
views
3-uniform hypergraphs and their circuit space
So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is ...
- 21
1
vote
0
answers
126
views
Algebraic structures on graphs
There are many algebraic structures linked to graphs.
For example one can find zero divisor graphs $[1]$, $[2]$ and many other graphs.
Does there exist any survey paper which characterizes all the ...
- 444
9
votes
3
answers
3k
views
What happens to eigenvalues when edges are removed?
I am stuck at the following :
Let $G$ be a graph and $A$ is its adjacency matrix.
Let the eigenvalues of $A$ be $\lambda_1\le \lambda_2\leq \cdots \leq \lambda_n$.
If we remove some edges from the ...
- 444
0
votes
0
answers
67
views
Singular values and the chromatic number
What relation, if any, is there between the singular values of the adjacency matrix ( or possibly incidence matrix) of a simple graph and its chromatic number. Typically, do we have Hoffmann type, or ...
- 2,089