All Questions
6,289 questions
10
votes
1
answer
5k
views
Eigendecomposition after multiplying by diagonal matrix
Hello,
If we possess the eigendecomposition of a positive definite matrix: $X = U \Sigma U^T$, is there an efficient way to compute the eigendecomposition of $D X D$ where $D$ is a diagonal matrix?
- 103
9
votes
1
answer
904
views
Reference for a formula expressing the characteristic polynomial of a sum of endomorphisms
Let $R$ be a ring, $A$ a (not necessarily commutative) $R$-algebra and $M$ a (left) A-module which is free of finite rank as an $R$-module. If $a\in A$ then multiplication with $a$ on $M$ is an $R$-...
- 1,645
2
votes
1
answer
200
views
Planar Graphs and Skew Binary Spaces
Let $G$ be a planar triangulation on $3m$ edges and $m+2$ vertices. Let $A$ be the binary matrix obtained from the incidence matrix of $G$ by deleting a row (equivalently we require the rows of $A$ to ...
4
votes
1
answer
535
views
A Question on Koszul duality and $B(\infty)$ structures on $HH^*$
The following theorem is known from a paper "Duality in Gerstenhaber Algebras" by Felix, Menichi, Thomas. Given a simply connected space X of finite type.
There is an equivalence of Gerstenhaber ...
- 3,758
8
votes
2
answers
2k
views
Algorithm for solving systems of linear Diophantine inequalities
So, I posted on StackOverflow looking for a reasonably fast algorithm to solve systems of linear Diophantine inequalities and was pointed to this article by Cheng-Zhi Gao and Yu-Lin Dong. The problem ...
- 3,079
0
votes
1
answer
503
views
When are operators extended by linearity bounded?
Greetings.
Suppose that $H$ is a separable infinite-dimensional Hilbert space and that $M$ is an infinite
dimensional closed subspace of $H$. Suppose that {$v_{n}: n\ge 1$} is an infinite linearly ...
- 129
4
votes
3
answers
2k
views
Spectral radius of a proper subgraph
I came across a Chinese reference in the paper "On the spectral radius of trees with fixed diameter" by Guo and Shao. The attribute the following to Q. Li, K.Q. Feng in: "On the largest eigenvalue of ...
- 475
4
votes
2
answers
3k
views
Monotonicity of the hard EM algorithm.
Consider the problem where we want to find a maximum likelihood estimate of $\theta$, given $X$ and $$P_\theta(Y) = \sum_z P_\theta(Y,x)$$ where $x$ is a latent variable.
I know that the soft EM ...
- 1,902
4
votes
1
answer
8k
views
Detection of Redundant Constraints
Suppose I pose the following query to a constraint logic programming
system:
?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3.
Are there systems that would recognize the last inequality as
...
Countably Infinite
1
vote
2
answers
763
views
A basis for $\mathbb{Q_p}$ as a vector space over $\mathbb{Q}$
I was looking for a reference that illustrates a $\mathbb{Q}$-vector space basis for the field of p-adic numbers under the following action. Given a rational number $q$. write, $q=\frac{m}{n}$ where $...
2
votes
1
answer
3k
views
Subtract diagonal terms from the matrix to make it negative semi-definite
I'm reading one paper and on page 36 (48 in the pdf) it says:
Let d(s, i) be the (positive) diagonal terms that need to be subtracted from the matrix to make it negative semi-definite...
...
- 219
22
votes
9
answers
17k
views
Fast evaluation of polynomials
Hello everybody !
I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
- 1,654
8
votes
1
answer
1k
views
Spectra of a Symmetric Toeplitz Operator
For a physics application, I would like to be able to compute the eigenvalues of the linear operator (acting on the Hilbert space $\ell^2$) given by an infinite matrix of the form
$\begin{bmatrix}
...
- 81
3
votes
3
answers
461
views
Multiplicity of eigenvalues in 2-dim families of symmetric matrices
Say you have 2 symmetric matrices, $A$ and $B$, and you know that every linear combination $xA+yB$ ($x,\\,y\in \mathbb{R}$) has an eigenvalue of multiplicity at least $m>1$. Such a situation can of ...
- 1,452
2
votes
2
answers
402
views
Maximization of a matrix product by iterative methods
This might not be very difficult, but I think I may have gotten a little confused.
Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...
- 949
3
votes
1
answer
321
views
spurious torsion under compositions of linear maps
Say we have a PID $R$, integers $1 \leq a \leq b$, and $R$-homomorphisms $R^a \stackrel f\to R^b \stackrel g\to R^a$ with $g \circ f$ of full rank.
For $h = f, g, g \circ f$, let $c(h)$ be the ...
- 735
1
vote
2
answers
2k
views
Complexity of EVD
What is the computational complexity of Eigen Value decomposition of a correlation matrix?
- 11
2
votes
1
answer
328
views
Doing column permutation under row overlap constraint
In coding theory, there are parity-check codes whose parity-check matrices $H$ are generated via column permutations. For instance, the binary LDPC codes constructed in Gallager's 1962 IRE Trans paper ...
- 285
5
votes
2
answers
475
views
Can finitely many hermitian (positive-semidefinite) operators always be embedded into a small dimensional space preserving inner product?
Given $n$ hermitian (positive-semidefinite) operators $Q_1,\cdots,Q_n$ in finite dimensional Hilbert space (the dimension can be very large), is there a mapping $\phi$ maps $Q_i$ to $P_i$, which ...
- 363
3
votes
3
answers
367
views
Info on Symplectic/Orthogonal groups of Gl(n,R); R a ring, not necessarily division ring.
Hi, Everyone:
Does anyone know anything about orthogonal and symplectic groups
associated to Gl(n,R)? I am using symplectic/orthogonal in what I think
is the standard sense; I mean, we have an R-...
- 63
8
votes
1
answer
1k
views
Bound on the von Neumann entropy of a positive, positive semi-definite, and unit-trace density matrix?
Can the von Neumann entropy of a positive, positive semi-definite, and unit-trace density matrix with equal on-diagonal terms be bounded by equalizing all off-diagonal elements to their highest/lowest ...
- 846
5
votes
1
answer
3k
views
Is there a closed form expression for the inverse of the matrix with elements $A_{i,j}=x_i$ for $i=j$ and $A_{i,j}=1$ for $i\neq j$?
Hello All
Consider a matrix with elements:
$A_{i,j}=x_i$ for $i=j$
$A_{i,j}=1$ for $i\neq j$
Is there a closed form expression for the elements of $A^{-1}$?
Will be glad to know of any reference.
...
- 53
5
votes
1
answer
183
views
Identification of conformal classes of pos def quadratic forms on R^2 with unit ball
One of the lemmas at the foundation of Teichmuller theory is as follows. Let $Q(x,y)$ be a positive definite quadratic form. Then there exists unique $\lambda \in \mathbb{R}$ and $\mu \in \mathbb{C}$...
- 53
1
vote
5
answers
452
views
Notation: Vector space spanned by all finite polynomials in $x$ and all finite polynomials in $y$
This is a simple question about notation: Given two generators $x,y$ how does one denote the vector space spanned by all finite K-polynomials in $x$ and all finite polynomials in $y$. If I use K**$[x] ...
- 1,479
4
votes
2
answers
3k
views
modified gram schmidt...
So I understand that the effective formula for the orthogonal basis of a matrix is the same in both modified and classical Gram Schmidt algorithm. Can someone explain whats the numerical instability ...
- 41
32
votes
3
answers
3k
views
How much linear algebra can be done with graphs?
Let G be a finite directed acyclic graph, with sources $A=\{a_1,\ldots,a_n\}$ and sinks $B=\{b_1,\ldots,b_n\}$, with edge weights $w_{ij}$. The weight of a directed path P is the product of weights of ...
- 22.1k
14
votes
3
answers
3k
views
Diagonalizing a Certain Real and Symmetric Toeplitz Matrix
Consider $0\leq \alpha\leq 1$, and let $A_{\alpha}$ be the Toeplitz $n\times n$ matrix given by
$$
A_\alpha := \begin{bmatrix}
1 & \alpha & \alpha^2 & \ldots &\alpha^{n-1} \\\
\alpha ...
- 3,626
16
votes
6
answers
13k
views
Showing block diagonal structure of matrix by reordering
Suppose we have a block-diagonal matrix $M$, but the block diagonal structure is not immediately apparent from looking at the matrix because the rows/columns are shuffled.
I wish to find a reordering ...
- 911
25
votes
4
answers
7k
views
"Natural" pairings between exterior powers of a vector space and its dual
Let $V$ be a finite-dimensional vector space over a field $k$, $v_1, \dotsc v_n \in V$ a set of vectors, and $f_1, \dotsc f_n \in V^{\ast}$ a set of covectors. Up to permutation, there seem to be at ...
- 118k
2
votes
3
answers
2k
views
Defining a canonical ordering of matrix rows/columns [closed]
I would like to find a way to define a canonical ordering of rows/columns in a matrix.
If two rows/columns cannot be ordered according to this canonical ordering (i.e. they're the "same"), then it ...
- 911
10
votes
1
answer
5k
views
Eigenvalues of the sum of a diagonal and a unit matrix
I'm trying to find information on the eigenvalues of an $n \times n$ matrix A such that
$A = D + J$
Where $D$ is some complex valued diagonal matrix, and $J$ is an matrix consisting of all $1$'s.
...
- 293
15
votes
2
answers
794
views
Invariants and orbits of $n$-tensors
My question may be absolutely elementary and is probably answered in 19th century. A reference or a short clear argument would be highly appreciated.
Let $V_1, \ldots V_n$ be finite dimensional ...
- 12.3k
2
votes
1
answer
1k
views
Condition for doubly non-negative matrices to be completely positive
Consider a doubly non-negative matrix $A$ of order $n$. $A$ is completely positive if and only if $A$ can be factorized into $BB^{T}$ where all entries in $B$ are non-negative. $B$ is $n\times k$. The ...
- 505
1
vote
1
answer
2k
views
Sufficient and necessary conditions on equality of Cauchy-Schwarz inequality of determinants
Cauchy-Schwarz inequality of determinants:
for $A_{n\times k}$, $B_{n\times k}$, and $B'B$ non-singular, we have
$|A'B|^2\leq |A'A||B'B|$
I was wondering what's the sufficient and necessary ...
- 13
2
votes
1
answer
292
views
nth-powers and degree n polynomials with coefficients in field extensions
Hi,
Suppose that $E/F$ is a Galois extension. If $P(X)\in E[X]$ is a (EDIT: monic) polynomial of
degree $n > 0$, such that $P(X)^n\in F[X]$, does it follow that $P(X)\in F[X]$?
Thanks
- 2,842
2
votes
1
answer
699
views
Symmetric Algebra [closed]
Consider V a vector space and the symmetric algebra $S(V^*)$
is it possible to define the polynomial on $V$, $R[V]$ canonically ?
I.e. without a use of base ?
And show this is isomorphic to the ...
- 221
7
votes
1
answer
2k
views
Determinant of a $4n \times 4n$ block matrix where every block is singular
I have a 4n$\times$4n matrix, which can be written as
\begin{pmatrix}
0 & A &B &C \cr
D& 0& E & F \cr
G& H & 0 & J \cr
K& L& M& 0
\end{pmatrix}
each ...
- 101
7
votes
1
answer
949
views
Norm of tridiagonal operator
Recently, I needed to estimate the operator norm of the tridiagonal operator, but I am sure answers much more refined than my simple observations must be known.
Let $T$ be the linear operator that ...
- 28.6k
6
votes
2
answers
3k
views
PSD matrix with non-negative entries
We have convex sets $C_1=Conv(yy^{T}|y^{T}y=a,y\in R^{M})$ and $C_2=Conv(yy^{T}|y^{T}y=a,y\in R_{\geq 0}^{M})$. Clearly $C_2\subset C_1$. Does there exist a PSD matrix $A$ having $tr(A)=a,A(i,j)\geq 0$...
- 505
2
votes
2
answers
468
views
Orthogonal transformations fixing a subspace (setwise)
Let $(V,Q)$ be a non-degenerate quadratic space of dimension $n$ over an algebraically closed field of characteristic zero. Let $W$ be a subspace of $V$ of dimension $m < \frac12 n$ which is ...
- 5,163
4
votes
2
answers
2k
views
Logarithm of a matrix
I am looking for a reference to study logarithm of an invertible triangular matrix. What is a good algorithm? Are there any good reference which studies this topic both theoretically and from an ...
- 13.9k
5
votes
4
answers
2k
views
Determining a recurrence relation
I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ ...
- 9,114
2
votes
1
answer
384
views
Feasible space of SDP
Typically the non-empty feasible space of a SDP has some curved boundary which is why the feasible space has infinitely many extreme points. Is it ever possible to have a SDP whose non-empty feasible ...
- 505
5
votes
2
answers
2k
views
rank-one perturbation of a matrix corresponding to a specific spectrum
Let $A$ be a real symmetric matrix whose spectrum is $\lambda_1,\lambda_2,\ldots,\lambda_n$.
Let $A'$ be the matrix obtained by adding a perturbation to $A$. The requirement is that only the second ...
- 111
3
votes
1
answer
250
views
action of SO(q)
Let $(V,q)$ be a non-degenerate quadratic space. Then we know that for any $d$ with $0 \leq 2d \leq \dim V$, the group $O(q)$ of isometries of $(V,q)$ acts transitively on the set of totally isotropic ...
- 5,163
4
votes
0
answers
3k
views
The determinant of the hadamard product of two matrices
We know that the determinant of a Hadamard product of two positive semidefinite matrices $|{\bf A}\circ{\bf B}|$ is greater than or equal to $|{\bf A}||{\bf B}|$. Are there any general results on ...
- 449
2
votes
4
answers
853
views
Generalization of scalar product to k-dimensional subspaces (as opposed to 1-dimensional subspaces, i.e. vectors)
This came up in a practical problem (physics).
In the following, we work with real numbers only, and consider every vector to be normalized to 1.
To find how "similar" two vectors are (actually, two ...
- 911
13
votes
2
answers
1k
views
Is the Characteristic of a Field Detectable from the Topology of a Topological Vector Space?
Motivation
A topological vector space is a vector space over a (topological) field, K, that carries a topology such that addition and scalar multiplication are continuous maps, e.g., all normed vector ...
3
votes
0
answers
242
views
Picking $n$ so that certain Schur functors of the standard representation of $S_n$ are linearly independent
Let $V_n$ be the standard permutation representation of the symmetric group $S_n$, and let $\mathbb{S}_{\lambda}$ denote the Schur functor associated to the partition $\lambda$.
Let $\lambda$ range ...
- 5,898
9
votes
3
answers
2k
views
On similar matrices and polynomial matrices
I'm teaching linear algebra and I'm encountering this theorem:
two matrices $A$ and B are similar iff $tI - A$ and $tI - B$ are equivalent (as polynomial matrices), where $I$ is the unit matrix.
The ...
- 357