Questions tagged [linear-algebra]
Questions about the properties of vector spaces and linear transformations, including linear systems in general.
5,875 questions
10
votes
5
answers
3k
views
Generalization of the polarisation formula for symmetric bilinear forms to symmetric multilinear forms
Given a symmetric bilinear form $f:V\times V \to K$ , where $V$ is a vector space and $K$ is an appropriate field, define the quadratic form $q:V \to K$ as $q(v):= f(v,v)$.
The Polarisation Formula ...
- 109
10
votes
1
answer
816
views
$\text{SL}_2(\mathbb{Z})$ and continued fractions?
I know the following facts: $\text{SL}_2(\mathbb{Z})$ is generated by everyone's favorite matrices
\begin{equation*}
S =
\begin{pmatrix}
0 & -1 \\
1 & 0
\end{pmatrix}
\end{equation*}
and
\...
- 1,075
10
votes
2
answers
614
views
Lower eigenvectors of nonnegative matrices with zero trace
Let $A$ be an $N\times N$ nonnegative matrix with all diagonal entries equal to zero and such that there is $n_0$ such that all entries of $A^{n_0}$ are strictly positive. Let $\lambda_1,\ldots, \...
- 1,897
10
votes
2
answers
427
views
Matrix exponential, containing a thermal state
This question was originally posted on MSE, and I'm cross posting it here.
Define an infinite matrix $$ M =
\begin{bmatrix}
0 & -1 & 0 & 0 & \cdots \\
1 & 0 & -2 & 0 &...
- 956
10
votes
2
answers
2k
views
Is there a standard name for (non-square) matrices with orthonormal columns?
One encounters often in numerics non-square matrices with orthonormal columns, i.e., $U\in\mathbb{R}^{m\times n}$, with $m > n$, such that $U^TU=I$ (but, clearly, $UU^T \neq I$).
Is there a name ...
- 20.2k
10
votes
1
answer
449
views
How to compute $\sum_{x \in \mathbb{Z}^n} e^{-x^TMx}$ efficiently
Let $M$ be a real symmetric integer valued positive definite matrix with $\det(M) \geq 1$. I would like write code to compute
$$S_M= \sum_{x \in \mathbb{Z}^n} e^{-x^TMx}.$$
One option is to simply ...
- 3,377
10
votes
5
answers
2k
views
The maximal eigenvalue of a symmetric Toeplitz matrix
Let $0\le x\le 1$ be a real number. Denote by $A_n(x)=(a_{ij})$ the $n$ by $n$ matrix such that $a_{ij}=x^{|i-j|}$ and let $\lambda_n(x)$ be the maximal eigenvalue of $A_n(x)$.
Is there any ...
- 1,418
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
10
votes
2
answers
2k
views
Largest rank submatrix of a skew symmetric matrix
Is the following statement true?
Given a skew symmetric matrix M, among all of its largest rank sub-matrix, there must be one that is the principal submatrix of M.
- 103
10
votes
2
answers
635
views
Largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$?
What is known about the largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$? I am especially interested when $q=2$, and in the regime where $k$ is fixed an $n\to\infty$. Here are ...
- 455
10
votes
1
answer
1k
views
Cryptographic Secret Santa
Is there a protocol for conducting a Secret Santa without a central authority? Precisely, we want to sample uniformly a permutation that has no one-cycles and reveal to each member his or her ...
- 101
10
votes
2
answers
733
views
Product $PVPVP$ is elementwise nonnegative?
Let $P\in \mathbb{R}^{n\times n}$ be the inverse of a positive definite M-matrix and $V\in \mathbb{R}^{n\times n}$ be any diagonal matrix. Prove (or disprove) that $PVPVP$ is elementwise nonnegative.
...
- 143
10
votes
2
answers
895
views
What norms can be "universally" defined on any real vector space with a fixed basis?
Let $V$ be a real vector space and let $B = (b_\lambda)_{\lambda \in \Lambda}$ be a basis. So every $v \in V$ can be written uniquely as a linear combination
$$ v = c_{\lambda_1} b_{\lambda_1} + c_{\...
- 641
10
votes
1
answer
262
views
What is the hidden symmetry behind four generic planes in $\mathbb{R}^4$?
Consider the action of $\operatorname{GL}(\mathbb{R}^4)$ on the Grassmannian of 2-dimensional subspaces of $\mathbb{R}^4$. In experiments, I observe that four randomly drawn points in this space are ...
- 7,633
10
votes
2
answers
711
views
Order of unipotent matrices over $\mathbb{Z}/q\mathbb{Z}$
Let $q$ be a prime power and let $n\geq2$ be an integer.
Is it known what is the largest order of a unipotent upper-triangular $n\times n$ matrix over the ring $\mathbb{Z}/q\mathbb{Z}$?
I am mostly ...
- 749
10
votes
1
answer
520
views
Homogeneous polynomials, mixed determinants, positive definiteness
Are there $n\times n$ real matrices $A_{1}, \ldots, A_{n}$ such that the $n$-homogeneous polynomial
$$
f(x_{1}, \ldots, x_{n}) = \det(x_{1} A_{1}+\cdots +x_{n} A_{n})
$$
never vanishes on $\...
- 3,946
10
votes
1
answer
4k
views
Eigenvalues, singular values, and the angles between eigenvectors
Suppose the $n \times n$ matrix $A$ has eigenvalues $\lambda_1, \ldots, \lambda_n$ and singular values $\sigma_1, \ldots, \sigma_n$. It seems plausible that by comparing the singular values and ...
- 571
10
votes
2
answers
1k
views
Does the hyperdeterminant calculate a quantity akin to the volume of a parallelepiped?
If $M$ is an $n \times n$ matrix, $|\det(M)|$ is the volume of the $n$-dimensional
parallelepiped spanned by the column vectors of $M$.
...
- 151k
10
votes
1
answer
923
views
Conjugation between commutative subalgebras of a matrix algebra?
Let $K$ be an algebraically closed field and $M_n(K)$ the $K$-algebra of all matrices $n\times n$ over $K$. If $L$ and $M$ are two isomorphic commutative subalgebras of $M_n(K)$, it is true that there ...
- 545
10
votes
2
answers
1k
views
Indecomposable vector spaces and the axiom of choice
It is a known result by A. Blass that the axiom of choice is equivalent to the assertion that every vector space has a basis. (Rubin's Equivalents of the Axiom of Choice: form B)
It is also known ...
- 39.8k
10
votes
1
answer
678
views
Sum of the coefficients of the characteristic polynomial of periodic matrices
Let $M$ be an integer matrix with determinant equal to one (or maybe also minus one, but I did not do any tests for this case) and assume that $M$ is periodic, that is $M^n$ is the identity matrix for ...
- 26.5k
10
votes
1
answer
2k
views
Multilinear generalization of Cauchy-Schwarz inequality
Let $V$ be a real vector space, and let $(\cdot,\cdot;\cdot,\cdot) : V^4 \to \mathbb{R}$ be a multilinear form with the following properties:
$(x,y;z,w) = (y,x;z,w) = (x,y;w,z)$ (symmetry in the ...
- 29.8k
10
votes
1
answer
1k
views
Bounds on $\|P^{k+1} - P^k\|$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k\gg n$
The problem:
We have a $n$-state Markov chain with arbitrary initial distribution and transition matrix $P$ that is arbitrary except that we know that $P$ has trace $n-1$. Of course $P$ is also a ...
- 303
10
votes
3
answers
6k
views
Solving a system of linear inequalities -- what is the dimension of the solution set?
It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$?
For the applications I have in mind the ...
- 7,857
10
votes
2
answers
478
views
Inequality for trace of a symmetric product?
Let $A$ be a real, positive-definite, symmetric operator on an $n$-dimensional space $V$. Write $\odot^k A$ for the action of $A$ on the symmetric power $\odot^k V$. Let $v_1,\dotsc,v_n$ be a basis ...
- 20.2k
10
votes
1
answer
483
views
functors $\text{Vect} \to \text{Vect}$ that preserve filtered and sifted colimits
I'm considering various functors from the category $\text{Vect}$ of real vector spaces to itself, and would like to know that they preserve filtered colimits and possibly even sifted colimits. The ...
- 1,092
10
votes
2
answers
2k
views
When is a bilinear form equivalent to a trace form?
Associated to a finite, separable field extension $L/K$, there is a natural nondegenerate bilinear form, the trace form, defined by $$\langle x,y \rangle := \mathrm{Tr}_{L/K}(xy)$$
Now, given a ...
- 1,142
10
votes
3
answers
321
views
Traces of powers of integral marices
I have encountered the following linear algebra/number theory question in my work (low-dimensional topology), so I thought I should ask the experts.
Let $A \in SL(n,\mathbb{Z})$ be a matrix , $n \geq ...
- 858
10
votes
2
answers
630
views
What are the invariants of $U\otimes V\otimes W$ under action of $GL(U)\times GL(V) \times GL(W)$
The tensor product of some (finite dimensional real) vector spaces is acted on by the direct product of their general linear groups. I would like to know if there are explicit invariants in the case ...
- 700
10
votes
1
answer
813
views
Linear system of equations with nonnegative solutions and a recursion rule
My question derives from reading a recent preprint (arXiv:1209.0827v1, in particular Section 4.1), but it can be phrased quite independently from that paper. The setup is as follows.
Let $A$ be the ...
10
votes
1
answer
1k
views
Intrinsic description of the image of $V \to V^{**}$
Let $V$ be a vector space over a field $K$. Call a linear map $F : V^* \to K$ representable if there is some $v \in V$ such that $F(w) = \langle w,v \rangle$ for all $w \in V^*$. Here, $\langle w,v \...
- 63.1k
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
10
votes
1
answer
866
views
Geometric meaning of unimodular matrix
Rotations are given by unitary matrices.
What is the geometric meaning of unimodular matrices that are not unitary?
user76479
10
votes
1
answer
938
views
Why does this antisymmetric product factor out a determinant?
Consider a generic $n \times n$ matrix $M$.
Define the $(n-1) \times n$ matrix $M_q$ to be $M$ with the $q$th row omitted, and assume that $M_q$ possesses a right inverse, $R_q$:
$$R_q = M_q^T (M_q ...
- 2,902
10
votes
2
answers
1k
views
Probability of random (0,1) Toeplitz matrix being invertible
A Toeplitz matrix or diagonal-constant matrix is a matrix in which each descending diagonal from left to right is constant.
What is the probability that a random $n \times n$ binary Toeplitz ...
user32786
10
votes
1
answer
2k
views
Over which fields is the Sylvester law of inertia valid?
Short version:
Over which fields is the (appropriate version of the) "Sylvester law of inertia" valid?
Long version:
Let $V$ be a finite dimensional vector space over the field $\Bbbk$ of ...
- 23.3k
10
votes
2
answers
2k
views
What is the canonical isomorphism between the tensor products of the top exterior powers associated to exact sequences of vector spaces?
One often reads (and writes) that an exact sequence of finite dimensional vector spaces
$$
0 \rightarrow X_1 \rightarrow X_2 \rightarrow \dots \rightarrow X_n \rightarrow 0
$$
induces a canonical ...
10
votes
2
answers
18k
views
Fast trace of inverse of a square matrix
Which would be the most efficient way (in computational time) to compute tr(inv(H)), where H is a (dense) square matrix?
In my particular problem I also have a LU decomposition of H already available,...
- 339
10
votes
1
answer
4k
views
Properties of Zero Line-Sum Matrices
By a Zero Line-Sum (ZLS) matrix I mean matrices with the property, that each row sum and each column sum equals zero:
$$A\in\mathbb{R}^{m\times n}:\ \sum_{i=1}^{n}a_{ij}=\sum_{j=1}^{m}a_{ij}=0$$
...
- 13.2k
10
votes
1
answer
615
views
A curious determinantal inequality I
Let $A, B$ be Hermitian matrices. Does the following hold?
$$\det(A^{2}+B^{2}+|AB+BA|)\leq \det(A^{2}+B^{2}+|AB|+|BA|)$$
As usual, $|X|=(X^*X)^{1/2}$. Clearly, quantities on both sides are no less ...
- 1,748
10
votes
1
answer
3k
views
Reverse Minkowski (and related) Determinant Inequalities
For positive semidefinite matrices $A,B,C \in \mathbb{R}^{n\times n}$, the following inequalities are well known:
$$(\det(A+B))^{1/n} \geq (\det A)^{1/n} + (\det B)^{1/n} $$
and
$$\det(A+B+C) + \...
- 716
10
votes
1
answer
366
views
Powers of traces, integrals over spheres and class functions
I asked this on math.StackExchange a while back but got no answers. I hope I'll be forgiven for the double post.
Let $V$ be a complex vector space of dimension $\operatorname{dim}_{\mathbb C} V = n$, ...
- 4,343
10
votes
1
answer
2k
views
Who first proved that the dimension of a vector space is unique?
every vector space is known to have a basis (assuming the axiom of choice). This is attributed to Georg Hamel (http://de.wikipedia.org/wiki/Georg_Hamel). Moreover, any two bases have the same ...
- 558
10
votes
3
answers
3k
views
The largest eigenvalue of a "hyperbolic" matrix
Given an integer $n\ge 1$, what is the largest eigenvalue $\lambda_n$ of the matrix $M_n=(m_{ij})_{1\le i,j\le n}$ with the elements $m_{ij}$ equal to $0$ or $1$ according to whether $ij>n$ or $ij\...
- 23k
10
votes
1
answer
319
views
Construction of skew-Hadamard matrix of order 292
I am currently looking into how to construct a skew-Hadamard matrix of order 292. Where can I find such construction?
According to multiple papers (e.g. Koukouvinos and Stylianou - On skew-Hadamard ...
- 261
10
votes
1
answer
466
views
Is there a pattern for the irreducible factors and degrees of a characteristic polynomial?
Let $Log(n) = \sum_{i=1}^r \alpha_i \cdot e_i$, where $n = \prod_{i=1}^r p_i^{\alpha_i}$ and $p_i$ is the $i$-th prime, $\alpha_i \ge 0$, $e_i$ is the $i$-th standard basis vector. For example $6 = 2\...
user6671
10
votes
2
answers
4k
views
SVD vs Fourier analysis for data.
Fourier analysis is useful for analysis in the frequency domain. SVD on the other hand is useful for analysis of data, and expressing noise in the data. I have a problem that needs extensive data ...
- 325
10
votes
1
answer
403
views
Wild classification problems and Borel reducibility
My question is whether the archetype of 'wild' problems in algebra, namely classifying pairs of square matrices up to similarity, is 'non-smooth' in the sense of Borel reducibility.
This was ...
- 22.3k
10
votes
2
answers
5k
views
Nuclear norm as minimum of Frobenius norm product
Nuclear, or trace, or Ky Fan, norm of a matrix is defined as the sum of the singular values of the matrix.
It is claimed that
$$
\|X\|_\sigma = \min_{UV^T=X} \|U\|\|V\| = \min_{UV^T=X} \frac{1}{2}(\|...
- 2,239
10
votes
1
answer
1k
views
Relationship between eigenvalues of $A-B$ and eigenvalues of $A^2-B^2$
Let us suppose that $A_{n}$ and $B_n$ are sequences of positive definite matrices satisfying
$$c \leq \lambda_{\min}(A_n)\leq \lambda_{\max}(A_n)\leq C$$
and
$$c \leq \lambda_{\min}(B_n)\leq \...
- 103