Tagged Questions

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 ...
263 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 ...
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 ...
148 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 ...
291 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 ...
173 views

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 ...
208 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 ...
208 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 ...
534 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$ ...
135 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 ...
358 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 ...
244 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) &lt; 0$; $\ast$-negative-stable ...
514 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). ...
235 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 ...