All Questions
6,288 questions
8
votes
2
answers
462
views
Projecting the unit cube onto subspaces
Given a set $S$ of non-zero vectors in $\mathbb{R}^n,$ and a subspace $L,$ consider $f(S,L)=\max_{s \in S}\frac{\|Ps\|_2}{\|s\|_2}$ where $Ps$ is the orthogonal projection of $s$ onto $L.$
...
- 30.1k
1
vote
0
answers
77
views
r-locally linear functions of many variables
Suppose $m,n,r$ are positive integers. Suppose V is a $m$-dimensional vector space over a field F. Let $G(V,n,r)$ denote the space of $n$-tuples of elements of V with the property that the vector ...
- 7,320
4
votes
1
answer
626
views
Embed the intersection of an n-dimensional unit $L_1$ sphere and a hyperplane into an (n-1)-dimensional unit $L_1$ sphere.
In $\mathbb{R}^n$, given an unit $L_1$ sphere $\mathcal{B}_n: |x_1|+|x_2|+\ldots+|x_n|\leq 1$ and a hyperplane $\mathcal{P}: a_1x_1+a_2x_2+\ldots+a_nx_n=0$. Does there always exist a rotation such ...
- 59
3
votes
1
answer
346
views
enlarge the separation between two matrices
The separation between two square matrices $A$ and $B$, often used as a measure of the sensitivity of invariant subspace problems, is defined as
$$
\operatorname{sep}(A,B)=\min_{X\neq 0}\frac{\left\...
- 20.2k
4
votes
3
answers
422
views
probability that a random element of Z/NZ can be written as a subset sum of others
How could one calculate the probability that any element in $\mathbb{Z}/N\mathbb{Z}$ can be written as a subset sum of $n$ random elements in $\mathbb{Z}/N\mathbb{Z}$?
In other words, say I pick $n$...
- 41
2
votes
2
answers
607
views
Projecting the unit cube onto a subspace [closed]
I have some (rather exotic) subspace $L<R^n$, and I want to show that every non-zero vector in $\{0,1\}^n$ has a relatively small projection onto $L$. What general results and tools can be helpful? ...
- 23k
5
votes
5
answers
2k
views
Topics for a matrix analysis course
I recently taught a new (to my department) course titled "Matrix Analysis". For various reasons that I won't go into here, I was dissatisfied with the textbook I (loosely) followed, and with every ...
3
votes
1
answer
218
views
decompositions of matrices over $\mathbb{Q}$
Given a matrix $A\in GL_n(\mathbb{Q})$. Can it be expressed as a product of two matrices $B,C$ with $B\in GL_n(\mathbb{Z}[1/p])$ and $C\in GL_{n}(\mathbb{Z}_{(p)})$, where $ \mathbb{Z_p}$ denotes the ...
- 11.1k
1
vote
1
answer
2k
views
Linear combination of orthogonal projection matrices
Hello!
Let $v_i\in R^d$ $(i=1,...,n,n>d)$ be unit-length vectors ($v_i^Tv_i=1$). Then $v_iv_i^T$ is an orthogonal projection matrix, which has many elegant properties. Now consider a linear ...
- 61
25
votes
2
answers
1k
views
Factorization of a real matrix into Hermitian x Hermitian. Is it stable ?
It is known (see Theorem 4.1.7 in R. Horn & C. Johnson) that every matrix $A\in M_n(\mathbb R)$ (real entries) can be written as the product $HK$ of two Hermitian matrices (complex entries). Of ...
- 52.3k
3
votes
4
answers
4k
views
Existence of nonnegative solutions to an underdetermined system of linear equations
Similar questions have been asked elsewhere, but I think this is sufficiently different to warrant a new post. I have a particular matrix $A$ and would like to know when the system $Ax = 0$ has at ...
- 491
3
votes
2
answers
5k
views
Elementary proof that the Hilbert Matrix is invertible with integer entries [duplicate]
Possible Duplicate:
Deriving Inverse of Hilbert Matrix
The inverse of the Hilbert Matrix is made up entirely of integer entries, but I can't seem to
find an elementary proof for that though, any ...
- 41
0
votes
2
answers
2k
views
How to accelerate/avoid multiplication for large matrices in Matlab? [closed]
The setting is here.
X: 6000x8000 non-sparse matrix
B: 8000x1 sparse vector with only tens of non-zeros
d: positive number
M: is sparsified X'X, i.e. thresholding the elements smaller than d ...
- 21
12
votes
3
answers
15k
views
Kind of submultiplicativity of the Frobenius norm: $\|AB\|_F \leq \|A\|_2\|B\|_F$?
Let $\|\cdot\|_F$ and $\|\cdot\|_2$ be the Frobenius norm and the spectral norm, respectively.
I'm reading Ji-Guang Sun's paper 'Perturbation Bounds for the Cholesky and QR Factorizations' from BIT ...
5
votes
2
answers
1k
views
Find the point on the Stiefel Manifold that is closest to a matrix
I don't have much background on high-dimensional geometry, so I dare to ask it.
For a given point in $x\in\mathbb{R}^n$, assume that I want to find the point on the unit sphere that is closest to the ...
0
votes
0
answers
1k
views
Determinant of special generalized Vandermonde matrix
Good evening!
I have a generalized Vandermonde matrix of special form:
$\left( \begin{array}{ccccc} a_{0,0} & a_{0,1} \cdot x_0 & a_{0,2} \cdot x_0^2 & \ldots & a_{0,m-1} \cdot x_0^{m-...
spk
9
votes
5
answers
5k
views
Use of traces in physics
This is borderline physics, but I'll post here first as it relates to a mathematical concept.
I was wondering if anyone could clarify what the physical significance is of traces, whether of matrices ...
11
votes
1
answer
3k
views
Best way to find a closest vector in a lattice
Let $v_1,\dotsc,v_n$ be linearly independent vectors in $\mathbb{R}^n$, and let $\Lambda=\bigoplus_{i=1}^n \mathbb{Z}v_i$. The question is, given a vector $w$ in $\mathbb R^n$, find the element $v$ ...
- 351
14
votes
1
answer
1k
views
A Question on Random Matrices
Consider the following $n\times n$ random matrix $V_{n}$ where the $(p,q)$ entry is given by
$$
V_{n}(p,q):= \frac{1}{\sqrt{n}}\exp(2\pi i(p-1) x_{q})
$$
where $x_{1},x_{2},\ldots,x_{n}$ are iid ...
- 3,626
2
votes
0
answers
520
views
Eigenvector of infinite matrix
I consider the system of reaction-diffusion PDEs in a ball
with Robin boundary condition.
It is a Steklov eigenvalue problem
(see G Auchmuty (2004) "Steklov eigenproblems and the representation
of ...
- 31
2
votes
1
answer
211
views
Nonsingularity of certain block matrices
I am completely stuck in the following linear algebra problem.
Consider a finite group $H$ and $N\times N$-matrices $M_{g,h}$ with entries in $\mathbb{Z}$ for all $g,h\in H$. Assume $\sum_{h\in H} ...
- 804
7
votes
2
answers
715
views
Bimodules over division rings
Inspired by other questions i have two questions about modules over division rings: given a division ring $D$ with center $Z(D)=K$. One has the notion of dimension for left modules (vector spaces) $V$ ...
- 1,391
1
vote
1
answer
2k
views
Can a complex non-skew Hermitian matrix have purely imaginary eigenvalues?
I am trying to determine if a certain matrix can have purely imaginary eigenvalues. My question in its most general form is weather a complex matrix that is not skew-Hermitian and irreducible can ...
- 599
4
votes
4
answers
703
views
efficient way to compute the inversion of the following matrix
Hi, there
I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special ...
- 41
3
votes
2
answers
1k
views
Hadamard product of matrices over finite field
Hello, all!
I consider Hadamard product $A \circ B$ of matrices $A$, $B$ over finite field. I know $\det{A}$ and $\det{B}$ and want to know about $\det{(A \circ B)}$. Wikipedia and Google let me know ...
spk
9
votes
2
answers
1k
views
Question on eigenvalue square root subadditivity
ORIGINAL QUESTION
Let $\lambda_{1}\left(\cdot\right)$ be the larger eigenvalue of a
$2\times2$ matrix and $\lambda_{2}\left(\cdot\right)$ the smaller
eigenvalue of a $2\times2$ matrix. Is it true ...
- 91
19
votes
1
answer
3k
views
Non-degenerate alternating bilinear form on a finite abelian group
I asked this question on math.stackexchange yesterday, but nobody has helped so far, and only 44 people have seen it! So I hope people do not mind me asking it here...
Let $A$ be a finite abelian ...
- 831
3
votes
2
answers
344
views
Pseudo-idempotent matrix generating a free module
Let $R$ be a commutative ring with $1$. Let $n$ and $k$ be nonnegative integers, and let $A\in\mathrm{M}_n\left(R\right)$ be a matrix such that $A\cdot R^n\cong R^k$ as $R$-modules. Assume that $A^2=\...
- 33.8k
2
votes
2
answers
861
views
Spectral gap of a product of Markov processes
For $m \in [N] \equiv \{1,\dots, N\}$, let $Q^{(m)}$ be the generator of a (well-behaved) continuous-time Markov process on a finite state space $[n_m]$. Write $J \equiv (j_1,\dots,j_N) \in \prod_m [...
- 15.4k
5
votes
2
answers
681
views
Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).
Is there an efficient algorithm for finding the solution $x$ of
$b = Ax$
that minimizes the Hamming weight of $x$, where
$A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo 2")...
- 141
3
votes
1
answer
358
views
Feasibility of a matrix equation
I am working on a problem where the following equation came up
$${\bf X}_1{\bf A}{\bf X}_2{\bf A}^T{\bf X}_3{\bf A}-{\bf X}_4={\bf A}$$
where ${\bf A}$ is an arbitrary $n\times n$ and ${\bf X}_i$s ...
- 449
5
votes
3
answers
590
views
Analogue Bialgeras vs Lie bialgebras
I once thought that the analogue of bialgebras and Lie bialegras is similar to that of (associative) algebras and Lie algebras, but it seems not that trivial.
Recall the definitions: a) bialgebra $A$...
- 1,271
6
votes
1
answer
11k
views
Number of n-th roots of unity over finite fields [closed]
How many $n$-th roots of unity does a finite field $\mathbb{GF}\left(p^k\right)$ have? ($p$ is prime). And then kind of related to that, is there a finite field with exactly $n_1,\ldots,n_N$ $n_1$-th,....
- 449
0
votes
2
answers
273
views
Nonexistence of projection
Following is a doubt I got when I was reading Csiszar's Annals of Statistics paper "Why least squares and maximum entropy: An axiomatic approach to inference for linear inverse problems".
He comes up ...
- 779
12
votes
1
answer
3k
views
invariant polynomials on 3 by 3 matrices
Hi there:
A freshman level question here. A polynomial p on the entries of n by n matrices is said to be invariant if p(A)=p(sAs^{-1}) for every invertible matrix s. For example, for 3 by 3 matrices, ...
- 141
3
votes
1
answer
1k
views
Recurrence Equations for Matrix Determinant
Context: I'm reading this paper http://portal.acm.org/citation.cfm?id=1382468
Definitions:
$B_1 = I$
$B_{k+1} = AB_k - \frac{1}{k} tr (AB_k)I$
$det(A) = \frac{(-1)^n}{n} tr(AB_n)$
Question: How ...
- 663
2
votes
2
answers
547
views
The product of non-commuting semisimple matrices need not be semisimple
In general when one proves that the product of semisimple (i.e. diagonalizable) matrices is semisimple one assumes they commute and are thus simultaneously diagonalizable, and then the result follows. ...
- 2,108
2
votes
1
answer
2k
views
Irreducible non-singular M-matrices and complex numbers
It is well known that a non-singular M-matrix that is irreducible has a strictly positive inverse (all entries $>0$).
An M-matrix is a matrix that has eigenvalues with positive real part, and the ...
- 599
6
votes
2
answers
1k
views
Minimizing determinant(Ztranspose.A.Z)
Let $A$ be a fixed positive semi-definite symmetric $m\times m$ matrix, and let $p$ be a fixed positive integer. Let $Z$ vary over all $m\times p$ matrices with orthonormal columns, and denote the ...
- 323
6
votes
1
answer
830
views
Dominant eigenvector of a real symmetric tridiagonal matrix
What is the most efficient way to calculate the dominant eigenvector of a real symmetric tridiagonal matrix? What's the corresponding time complexity bound?
Could someone give me a reference for ...
- 61
13
votes
1
answer
13k
views
Eigenvalues of submatrices
I am interested in results on the eigenvalues of submatrices.
Given a symmetric and positive-semidefinite matrix $M$, denote the submatrix obtained by deleting the ith column and jth row as $[M]_{ji}$...
- 599
6
votes
1
answer
1k
views
Nilpotent matrices related to Lie algebras of special orthogonal groups in characteristic 0
In terms of matrix theory, the question I'm led to is the following: Start with an $n$-dimensional vector space over an algebraically closed field of characteristic 0 such as $\mathbb{C}$, which has ...
- 52.9k
4
votes
2
answers
633
views
A Question about Orthogonal Operators
Let $X$ be a finite-dimensional inner product space, and $T$ a linear operator on $X$. Let $W$ be a subset of $X$ with the following property:
If $T$ preserves norms on $W$, then $T$ is orthogonal on ...
- 363
11
votes
1
answer
1k
views
Proof of the "Neo-classical Inequality", a fractional extension of the binomial theorem
I came across the following inequality, dubbed the "Neoclassical Inequality" which holds uniformly in $p\geq 1$ and $n\in\mathbb N$:
$$\frac{1}{p^2}\sum_{j=0}^n\frac{a^{\frac{j}p}b^{\frac{n-j}p}}{\...
- 4,952
8
votes
2
answers
2k
views
Proof of a fact about traces
I'm following the open courseware content on Machine Learning from Stanford University. In the lecture notes, it is given that
$$\Delta_A \ tr(ABA^TC) = CAB + C^TAB^T$$
which I tried but couldn't ...
- 497
0
votes
1
answer
249
views
Going from individual elements back to to matrix/vector notation [closed]
Note: Moved to math.stackexchange.com. Sorry for the off-topic question!
[Context: I'm working through problem set one of Andrew Ng's Machine Learning course, question 2, trying to derive the Hessian ...
- 101
0
votes
2
answers
2k
views
decomposition of an orthogonal matrix
Hi,
I have a matrix : $W=I+U^TV$
$dim(W)=(D,D)$
$dim(U)=dim(V)=(N,D)$ with $N < < D$
I need it to be orthogonal ie $W^TW=I$
which gives me : $V^TU+U^TV+V^TUU^TV=0$
From that point, i ...
- 133
3
votes
1
answer
2k
views
Singular values of differences of square matrices
Suppose $A, B \in \mathbb{R}^{n \times n}$. Let $\sigma_1(A),\ldots,\sigma_n(A)$ be the singular values of $A$, and let $\sigma_1(B),\ldots,\sigma_n(B)$ be the singular values of $B$. If I know these ...
- 794
28
votes
4
answers
2k
views
Matrices: characterizing pairs $(AB, BA)$
Let $A$ be an $m\times n$-matrix and $B$ an $n \times m$-matrix over the same field. Consider the matrices $C=AB$ and $D=BA$. It is probably well known (and not difficult to show) that the only ...
- 6,919
0
votes
1
answer
879
views
identity for matrices whose determinant is 1.
For any matrices $A$,$B$ in $SL(2,\mathbb{C})$, let $M(A,B)$ be the 4 by 4 matrix whose columns are matrices $I$,$A$,$B$,$AB$. Then it is not hard to verify that $det M(A,B)= 2- tr[A,B]$.
Is there an ...
- 159