Skip to main content

All Questions

Tagged with
Filter by
Sorted by
Tagged with
2 votes
0 answers
35 views

Limiting spectral distribution of a random matrix with specific structure

First, consider an $N \times N$ Hermitian random matrix $V$ from the Gaussian Unitary Ensemble (GUE). It is well known that the empirical spectral distribution of the GUE satisfies the semicircle law ...
Sven Krug's user avatar
4 votes
1 answer
421 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 ...
mathoverflowUser's user avatar
1 vote
0 answers
48 views

How to solve a optimal matching problem where the "quality" of matching is only determined once all nodes are matched

Note: I'm not a mathematician; I'm just a biologist with basic math background trying to solve a scientific problem, so please excuse my ignorance. The gist of the problem is as follows: I have two ...
Rishika Mohanta's user avatar
1 vote
0 answers
134 views

Number of ways to place 4 kings on nxn chessboard

I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example: In the case where the $4$...
Cardstdani's user avatar
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 ...
user531465's user avatar
0 votes
0 answers
37 views

Largest root of the Adjacency matrix of two graphs (comparison)

Let $G$ and $H$ be two graphs whose spectral radius (largest eigenvalue) of the adjacency matrix is the largest root of the following polynomial: $$P_G(x) = x^6-x^5-(2a-n+5)x^4+(2a-n+1)x^3+2(5a-3n+5)x^...
User8976's user avatar
  • 199
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 ...
patchouli's user avatar
  • 275
1 vote
0 answers
122 views

Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?

In short, I found an algorithm for GI and the only hard instances I found so far are non-isomorphic strongly regular graphs with large automorphism groups. Q1 What are hard instances for the ...
joro's user avatar
  • 25.4k
2 votes
0 answers
203 views

Permutation similarity of matrices with many distinct entries

This is related to graph isomorphism. Here matrices are square $n \times n$ with non-negative integer entries. Two matrices $A,B$ are permutation similar if there exist permutation matrix $P$ such ...
joro's user avatar
  • 25.4k
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=\...
ABB's user avatar
  • 4,058
6 votes
1 answer
517 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 ...
ABB's user avatar
  • 4,058
1 vote
1 answer
143 views

Eigenvalues of directed graph with one outward edge for each vertex

I am concerned with unweighted directed graphs where each node contains exactly one edge pointing to another node, which could be itself. In other words, each row of the adjacency matrix contains one ...
user3433489's user avatar
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} ...
Xiangjie Ding's user avatar
2 votes
1 answer
155 views

What is the name of a matrix operation using the OR operator instead of addition?

Let's say we have two matrices $M$ and $G$ with $G, M \in \{0, 1\}^{n, n}$, we denote by $m_{i, j}$ the element of $M$ in the $i^\text{th}$ row and $j^\text{th}$ column, same for $G_{i, j}$. Let's ...
recouer's user avatar
  • 31
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 ...
Andrea's user avatar
  • 21
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 ...
Benjamin van Heerden's user avatar
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 ...
joro's user avatar
  • 25.4k
2 votes
0 answers
116 views

Intuition behind eigenvalues of a graph mattering

Is there a good intuition behind why the eigenvalues of a matrix corresponding to a graph tell us useful information about the graph? There are a lot of results relating the eigenvalues of the ...
JoshuaZ's user avatar
  • 6,969
1 vote
1 answer
165 views

Combinatorial graph optimization problem on integer adjacency matrices

We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers. Let $z_{i,j}:=\frac{M_{i,j}}{M_{i,j}+\sum_{k\neq i,j}\min(M_{i,k},M_{k,j})}$ for all $1\le i<j \le n$, and $z:=\...
Penelope Benenati's user avatar
2 votes
1 answer
156 views

Minimal Laplacian spread of a graph

Laplacian spread of a graph is the difference among the largest and the second smallest Laplacian eigenvalue of the graph. Is there any result or conjecture that discusses about the graphs having ...
Anđela Todorović's user avatar
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 (...
Daniel Krenn's user avatar
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 ...
joro's user avatar
  • 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 ...
Matthieu Latapy's user avatar
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 ...
Gordon Royle's user avatar
  • 12.7k
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 ...
Honza's user avatar
  • 419
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, ...
Honza's user avatar
  • 419
0 votes
2 answers
163 views

Graphs vs matrices (when $0$ weight edges are allowed) [closed]

EDIT: I have asked for closing this question, and posted an improved version on math.se. I hope this is ok. It is often claimed, including by myself for the last 20 years, that matrices are ...
Matthieu Latapy's user avatar
2 votes
0 answers
119 views

Complete graph invariant based on integer programming?

Roughly speaking, we are trying to find complete graph invariant as the lexicographically first matrix from the permutations of the adjacency matrix. Let $G$ be graph, possibly directed graph, of ...
joro's user avatar
  • 25.4k
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 $...
Mare's user avatar
  • 26.5k
2 votes
0 answers
154 views

What characterizes the incidence matrix of a tripartite hypergraph?

The incidence matrix of a graph $G = (V,E)$ is a matrix with $|V|$ rows and $|E|$ columns, in which element $v,e$ is $1$ if node $v$ is incident to edge $e$, and $0$ otherwise. In bipartite graphs, ...
Erel Segal-Halevi's user avatar
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 ...
G. Panel's user avatar
  • 449
1 vote
1 answer
848 views

Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]

If so, could you provide examples and specify the conditions under which this occurs? Thank you in advance
DanteAligante's user avatar
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 ...
Anup Anand Singh's user avatar
2 votes
0 answers
515 views

Normalized Laplacian matrix versus walk Laplacian matrix (or normalized adjacency matrix versus walk adjacency matrix)

In graphs, found that two different normalization matrices exist for Laplacian and adiacency matrix. I will ask about the adjacency matrix (for the Laplacian matrix the questions are the same). The ...
volperossa's user avatar
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 $\...
H A Helfgott's user avatar
  • 20.2k
1 vote
1 answer
60 views

Rank and edges in a combinatorial graph?

Fix a $d\in\mathbb N$ and consider the matrix $M\in\{0,1\}^{2^d\times d}$ of all $0/1$ vectors of length $d$. Consider the matrix $G\in\{0,1\}^{n\times n}$ whose $ij$ the entry is $0$ if inner product ...
Turbo's user avatar
  • 13.9k
0 votes
1 answer
154 views

Energy of a symmetric matrix with $0$, $1$ or $-1$ entries

I have a symmetric matrix with entries $0$, $1$ or $-1$ which appeared in my works in graph theory (the diagonal entries are all zero). I need a good upper bound for the energy of this matrix; i.e. "...
A. Mpi's user avatar
  • 351
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$...
Piero Giacomelli's user avatar
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 ...
Nick Dong's user avatar
  • 211
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 ...
David Roberson's user avatar
2 votes
2 answers
234 views

Adjacency matrix of total graph

Is there a nice way of relating the adjacency, incidence , Laplacian matrices and other matrices associated to a graph of a total graph with its original graph, or, say, at least relating that of the ...
vidyarthi's user avatar
  • 2,089
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&...
Amin235's user avatar
  • 313
0 votes
1 answer
125 views

Estimating Maximal-Clique of Metric Graphs via the Rank of their Adjacency Matrix

Let $\mathrm{M}\in\lbrace0,1\rbrace^n$ be the adjacency matrix of a graph $\mathrm{G}\left(V,E\subseteq\lbrace\lbrace u,v\rbrace| u,v\in V\rbrace\right)$ of order $n$. Let $\mathrm{G}$ ...
Manfred Weis's user avatar
  • 13.2k
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(...
John's user avatar
  • 193
2 votes
0 answers
203 views

Space of change of basis matrices between two similar matrices - how to reduce it with additional tests?

Assume we have two real symmetric $n\times n$ matrices: $A, B$. We can easily test their similarity: $\textrm{Tr}(A^k)=\textrm{Tr}(B^k)$ for $k=1..n$. In this case both can be rotated to the same ...
Jarek Duda's user avatar
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)$. ...
bodhisat's user avatar
1 vote
1 answer
123 views

Walks of odd Lengths in a Matrix

Consider the following matrix $$ A=\left[ \begin {array}{cccc} 1&1&0&0\\ 0&0&1&0\\ 0&0&1&1\\ 1&0&0&0 \end {array} \right]. $$ Assume that $B=A^k$ ...
user0410's user avatar
  • 211
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 ...
Gabe K's user avatar
  • 6,001
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 ...
BenjixLeGaulois's user avatar
0 votes
0 answers
189 views

The algebraic connectivity of $P_n$, the path on $n$ vertices does not exceed $\frac{12}{n^2-1}$

The algebraic connectivity of $P_n$, the path on $n$ vertices does not exceed $\frac{12}{n^2-1}$. Let algebraic connectivity of $P_n$ be denoted by $\mu$. I have proved a result that if $G$ is a ...
User8976's user avatar
  • 199