New answers tagged

0

Counting the number of even and odd sized subsets of a set $A$ of size $n$: $P(A)$ has a structure of vector space over $\mathbb F_2$ with the symmetric difference. Equivalently, one just takes the characteristic vectors in $\mathbb F_2^n$ with the usual addition. The even sized subsets form a subspace $W$. The odd sized is then the “affine” subspace $W+{...


10

When $m$ is prime there is a simpler proof. The Smith normal form of the character table of $S_n$ is computed at Problem 14 here (solution here). From this it follows that the rank of the character table mod $m$ equals the number of partitions of $n$ for which every part has multiplicity less than $m$. By a simple generating function argument (generalizing ...


13

This is true when $m$ is prime and false in general. Counterexample. Take $S_8$ with $m=6$. Computer calculations show that the $\mathbb{Z}$-rank of the character table of $S_8$ with entries taken modulo $6$ to lie in $\{0,1,2,3,4,5\}$ is $22$. Thus this matrix has full rank, equal to its number of columns. (Its rank as a matrix with entries in $\mathbb{Z}/6\...


2

Let $U$, $V$ be the image and kernel of $P$, respectively. Then $\mathbb{C}^n=U\oplus V$ and $$ \|P\|\leqslant C\,\, \text{for some}\,\,C>1\Leftrightarrow \forall u\in U, v\in V\colon\,\|u\|^2\leqslant C^2 \|u+v\|^2 \\ \Leftrightarrow \forall u\in U, v\in V\colon\,0\leqslant (C^2-1) \|u\|^2+2C^2 \Re \langle u,v\rangle+C^2 \|v^2\|\\ \forall u\in U, v\in V,...


5

Your question is essentially answered in a math.SE post by Asaf Karagila, but I think it is worth spelling out a subtle point. The axiom of multiple choice (or MC for short) says: For every set $X$ of nonempty sets, there exists a function $f$ on $X$ such that for every $x\in X$, $f(x)$ is a finite nonempty subset of $x$. In Lemma 2 of Some theorems on ...


1

If you have an account in springer you can see here: https://link.springer.com/chapter/10.1007%2F978-1-4615-4819-5_23


4

The paper which actually was Landau's first scientific paper written at the tender age of 18, was published in his Collected Works, vol. 1. In it, he proposes to rank chess players having played a round robin tournament according to an eigenvector of the results matrix . A much more comprehensive analysis of this method with the help of the (then new) Perron-...


11

The idea of PseudoNeo's comment settles the converse of my statement modulo that he missed four cases. According to the theory of indecomposable modules of the Dynkin quiver $D_4$ with all arrows pointing to the central node there are $12$ cases corresponding to the $12$ positive roots of the Lie algebra of type $D_4$. These cases for $(V;W_1,W_2,W_3)$ are $...


1

The characteristic polynomial is $$P(\lambda) = (\lambda+1)\left(\lambda^3 + \frac{\kappa+1}{\kappa} \lambda^2 + \frac{k-\beta+1}{\kappa} \lambda + \frac{k}{\kappa}\right) $$ Since $\kappa \lambda^3 + (\kappa+1) \lambda^2 + (k-\beta+1) \lambda + k$ is irreducible over the rationals, there's no further factorization possible: if you want explicit expressions ...


5

You can easily get a slightly cruder bound $d/n$ (or, if you want, $r/n$) as follows. Let $A_n=(T^*)^nT^n$ and $B_n=A_n-A_{n+1}$. Then $(B_nv,v)=\|T^nv\|^2-\|T^{n+1}v\|^2\ge 0$, so $B_n$ is positive definite. Also $B_{n+1}=T^*B_nT$, so, since $T$ is a contraction, $Tr B_{n+1}\le Tr B_n$ (this is obvious if $T$ is diagonal but in general $T=R_1DR_2$ where $...


2

A speech recognition practitioner here. SVD is used in certain algorithms, although not very ubiquitous. I am reminded of the fast speaker adaptation algorithm fMLLR[1], dated, but involving a clever and beautiful shuffling of matrices. SVD may not be the very core of it, but does make an appearance; also, the algorithm as such is indeed inspired by the PCA. ...


2

It was shown that many quantum algorithms (e.g. linear systems, Hamiltonian simulation, quantum phase estimation) can be thought of essentially as applications of the Quantum Singular Value Transform (QSVT). Even more recently, it was proposed that QSVT could lead to a Grand Unification of Quantum Algorithms. Here is a recent talk given on the latter paper.


5

The SVD is used to analyze linear regularization methods for linear inverse problems. Here is very short introduction: A linear inverse problem is the challenge to find a good approximation of a linear operator equation $Ax=b$ when $b$ is only given with an error, i.e. you only get $b^\delta$ with $\|b-b^\delta\|\leq\delta$ for some known $\delta>0$. Here ...


5

$\newcommand{\RR}{\mathbb{R}}$Filtering an image $u\in\RR^{n\times m}$ by some filter $h\in \RR^{2r+1\times 2s+1}$ means computing $$ \sum_{k=-r}^r\sum_{l=-s}^s u_{i+k,j+l}h_{k,l} $$ at every pixel $(i,j)$. This is basically a convolution (up the reflection of $h$). To compute one pixel of the filtered image, one needs $O((2r+1)(2s+1))$ operations. If the ...


6

In Positron Emission Imaging, scans take long time (>10 mins) and obviously this is affected by patient motion, one of the main factors being respiratory motion. Patients breathe, so they "blur" the image. A good way to fix this is to "bin" your data in different parts of the respiratory phase, i.e. reconstruct 10 images instead of 1, ...


3

SVD is often used to perform tensor decompositions in Tucker and Tensor Train formats. HOSVD (Higher-order SVD) is an algorithm that approximates a given tensor (a multidimensional array of real or complex numbers) with a smaller tensor and a bunch of matrices - this is called the Tucker format. Sometimes HOSVD is used to initialize such a decomposition ...


4

See my other answer for the caveat that I am writing about things I have learned from student presentations, so they may be flawed. Suppose we have a block of raw material which has some shape $X \subset \mathbb{R}^3$. We want to mold it into a new shape $Y \subset \mathbb{R}^3$, but, if the material is stretched too much, it will break. How can we model ...


12

I teach a course on Applied Linear Algebra, intended for Engineers, where the final project is always to give a presentation on an application of linear algebra in the student's field of study. Since I myself am not an engineer, I often learn new things here, but there is the risk that my level of understanding is no better than an undergraduate engineer. ...


3

Google Scholar turns up a lot of applications in cryptography. One reference that is very accessible to students (but not particularly deep) is "Singular Value Analysis of Cryptograms", Cleve Moler and Donald Morrison, MAA Monthly, Feb. 1983 vol 90., no. 2, pp. 78-87. It's available on JSTOR. http://www.jstor.com/stable/2975804


3

For an image compression example which can be used directly in teaching, see my answer at What is the intuition behind SVD?. I hope this example also serves to give some interesting insights into the svd!


4

In statistics, the SVD can be used to assess the conditioning of a design matrix, and thus the stability of the parameter coefficient estimates. One key advantage of this approach over the more common Variance Inflation Factors (VIF) is that it also allows detecting collinearity with the intercept column. One disadvantage is that it is much harder to explain ...


5

In control theory, specifially in $H_2/H_\infty$ or $\mu$ synthesis and analysis, pretty much everything relies on the SVD. For further info, see e.g. SVD controllers for $H_2$, $H_\infty$ and $\mu$ optimal control


0

Unfortunately there is no magic bullet method (apart from general Strassen-type algorithms that usually do not pay out in practice). Or, at least, if it existed, many of my colleagues and I would be surprised and happy to know about it. :) You can truncate the Neumann series $A^{-1} = I + M + M^2 + \dots$, but this is going to be a poor approximation unless $...


8

A huge amount of the work in analyzing measurements of earth's atmosphere in order to assess climate variability consists of clever applications of the SVD. See for example this paper by Coughlin and Tung or these notes from a course taught by Dennis Hartmann (which was my intro to the subject).


10

In quantum physics, one often studies the entanglement between to parts of the system, in terms of the entanglement entropy, which can be expressed in terms of the Schmidt coefficients occurring in the Schmidt decomposition (more or less an SVD) of a pure state. In particular the entanglement entropy $S$ is given by $$ S = - \sum_i |\alpha_i|^2 \log (|\...


9

It is a fun little exercise to show using SVD that a linear transformation $A\colon\mathbb{R}^n\to\mathbb{R}^n$ maps ellipses to ellipses (not necessarily centered at the origin). Given an ellipse $E$, find a linear transformation $B$ such that $B(E)$ is a sphere, say, by rotating $E$ around the origin such that the axes of the ellipse become parallel to the ...


5

I will assume that using just the singular values (rather then SVD as a whole) counts. Identify the space of symmetric positive-definite $n\times n$ real matrices with $\operatorname{GL}(n,\mathbb{R})/\operatorname{O}(n)$ by mapping $A\mapsto AA^\top$. Then the heat kernel $K(X,Y)$ with respect to the Riemannian structure carried over from the homogeneous ...


3

I consider the situation over $\mathbb{C}$. We can replace $G$ by the subgroup generated by the $g_j$'s, so assume that $G$ is generated by the $g_j$'s. That $G$ contains a spanning set of the space of all matrices yields that the center of $G$ only contains scalar matrices, and also that the inclusion $G \hookrightarrow \operatorname{GL}(n,\mathbb{C}) $ is ...


0

If you have access to a soft as Maple , Mathematica or Sage, you can proceed as follows. Let $A,B\in \mathrm{SL}_2$ be conjugate. Step 1. Using a Grobner basis library, you solve the equation in $X=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ $XB-AX=0,\det(X)=1$ ($5$ equations in the $4$ unknowns $(a_{i,j}))$. Since the dimension of the algebraic set of the ...


4

For $n :=\{0,1,\dots,n-1\}\in\omega$ let’s denote $P_n:\mathbb{R}^\omega\to \mathbb{R} ^n$ the projection, which is the restriction map $f\mapsto f_{|n}$. The dimensions of the subspaces $P_n(L)\subset \mathbb{R} ^n$ can’t be stationary, because that would mean that for some $n_0$, every function $f\in P_{n_0}(L)$ has a unique extension to a function $\...


2

You may want to use the following two facts: Minus the logarithm of an uniform distribution on $[0,1]$ is an exponential distribution (easy). An exponential distribution is infinitely divisible as a member of the family of Gamma distributions. Simulation of Gamma distributions is extensively discussed in the literature. In particular, if $Y_i,Y_j$ are two ...


12

See Remark 2.2 here. If you expand $p/q$ into a continued fraction then the successive convergents, as columns of a $2 \times 2$ matrix, have determinant $\pm 1$. Provided $p/q$ is in reduced form and $q > 0$, the last convergent $p_n/q_n$ in the continued fraction for $p/q$ will have $p_n = p$ and $q_n = q$. Let the second to last convergent be $p_{n-1}...


7

The paper Products of orthogonal projections shows in Theorem 1 that any singular matrix with norm less than $1$ is a product of projection matrices and gives an estimate on how many projection matrices you need. You can always scale a nilpotent matrix to have norm less than $1$ and so you can obtain a nilpotent matrix of any index that is a product of ...


5

I think your example is easily generalisable for any index. For example, let $$ Q_1=P_1\oplus(1), Q_2=P_2\oplus(1), Q_3=P_3\oplus(1)=(1)\oplus P_1, Q_4=(1)\oplus P_2, Q_5=(1)\oplus P_3. $$ Then $Q_5Q_4Q_3Q_2Q_1$ is nilpotent of index 3, and I think that a similar construction with $2n-1$ matrices of size $n$ gives nilpotence of index $n-1$.


1

This largest singular value is the norm of the matrix. You can use a net argument to show that there is a $C$ so that $$\mathbb{P}(\| A \|_{op} \geq C\sqrt{N}(\sqrt{\alpha} + \sqrt{1 - \alpha} + t)) \leq 2 e^{-Nt^2}$$ for all $\alpha, t$. For a reference, this appears as Theorem 4.4.5 in Vershynin's High Dimensional Probability book.


8

Consider the involution which complements the ''free'' entries in the reduced row echelon form of the matrix representing a subspace. That is, we leave the pivots as well as things that are necessarily zero unchanged while changing everything else. This involution has a single fixed point, e.g. $$\begin{bmatrix} 0 & 0 & 0 & 1 & 0\\ 0 & 0 &...


5

$\DeclareMathOperator\Un{Un}\DeclareMathOperator\Gr{Gr}$Let $\Un_n(K)$ be the group of upper triangular matrices over the field $K$ with diagonal $1$. It acts on the $d$-Grassmannian $\Gr_{n,d}(K)$, with, for $0\le d\le n$, a single fixed point, namely the subspace $K^d\times\{0\}^{n-d}$. Now suppose that $K$ is a finite field of characteristic $2$. Then $\...


0

I know that the limiting eigenvalue distribution satisfies a variational principle (see e.g. the joint work with A. Kuijlaars Large Deviations for a Non-Centered Wishart Matrix) from which you may derive a degree three algebraic equation for the Sieltjes transform, and eventually recover an analytic formula for the limiting density using the Cauchy–Plemelj ...


1

See Appendix A in M. Borovoi and D. A. Timashev, Galois cohomology and component group of a real reductive group.


2

Following the ideas from my answer to Carlo's question, let $M(z_1, \ldots, z_n)$ be the symmetric matrix with $M(z_1, \ldots, z_n)_{ij} = \Sigma_{ij}$ for $i \neq j$ and $M(z_1, \ldots, z_n)_{ii} = z_i$. Use any sort of numerical optimization algorithm to maximize $$\log \det M(z_1, \ldots, z_n) - \sum_{i=1}^n \Sigma^{-1}_{ii} z_i$$ on the open set of $(z_1,...


13

The conjecture is true. More precisely, here is what I will prove: Theorem Partition $\{ (i,j) : 1 \leq i \leq j \leq n \}$ into two disjoint sets, $A \sqcup B$. Let $X$ and $Y$ be positive definite $n \times n$ matrices and suppose that $X_{ij} = Y_{ij}$ for $(i,j) \in A$ and $(X^{-1})_{ij} = (Y^{-1})_{ij}$ for $(i,j) \in B$. Then $X = Y$. Lemma 1 Consider ...


Top 50 recent answers are included