# All Questions

Tagged with graph-theory matrices

65
questions

**7**

votes

**0**answers

156 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 $\...

**1**

vote

**1**answer

47 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 ...

**0**

votes

**1**answer

68 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. "...

**2**

votes

**1**answer

159 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$...

**2**

votes

**2**answers

140 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 ...

**9**

votes

**0**answers

228 views

+50

### Correspondence between matrix multiplication and a graph operation of Lovasz

In his book "Large networks and graph limits" (available online here: http://web.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf), Lovasz describes a multiplication operation (he calls it ...

**2**

votes

**2**answers

150 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 ...

**5**

votes

**1**answer

291 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&...

**0**

votes

**1**answer

53 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}$ ...

**1**

vote

**0**answers

62 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(...

**2**

votes

**0**answers

145 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 ...

**6**

votes

**1**answer

239 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)$.
...

**1**

vote

**1**answer

113 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$ ...

**2**

votes

**1**answer

139 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 ...

**0**

votes

**0**answers

97 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 ...