Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

0
votes
0answers
18 views

Complexity of the Product of 2 Orthonormal Matrices

I have two $n \times n$ matrices $A$ and $B$ which are both orthonormal and would like to calculate the product $A^TB$. Is there a way to exploit the orthonormal nature of the matrices to calculate ...
1
vote
2answers
129 views

Is there a compelling reason for the $lcd$ per se and $lcd\equiv lcm$ in fraction arithmetics?

I haven't done arithmetics during the past few years, so I'm filling the gaps before I'm starting out in math in a month, so I have little understanding of the numerics. I've come across such a gap ...
1
vote
1answer
69 views

Iteration to find squre root of positive semidefinite matrix

Suppose matrix $A$ is positive semidefinite and $I\succeq A$. Prove that the iteration $$Y_0=0,\hspace{3mm} Y_{n+1}=\frac{1}{2}(A+Y_n^2)$$ is nondecreasing (that is, $Y_{n+1}\succeq Y_n$ for all ...
0
votes
1answer
40 views

In linear iteration, find values for a,b that cause different outcomes

When iterating the equation $X_n=AX_0 + B$ for some initial value $X_0$, I need to find concrete values for $A$ and $B$ that: 1) cause the series to converge for some initial value $X_0$ and diverge ...
1
vote
1answer
163 views

How do deal with a giant sparse matrices?

Someone point me in the right direction. I'm looking to do some heavy-duty manipulation of some really large and often very sparse matrices. Naturally, this problem overlaps programming heavily (I ...
1
vote
1answer
149 views

Ideas on matrix factorizations and/or transformations for $\ell_1$ minimization

I am starting with a typical $\ell_1$ basis pursuit problem: $$ \min_{\mathbf{x}} \Vert \mathbf{x} \Vert_1 \quad \mathrm{s.t.} \quad \Vert \mathbf{ERx} - \mathbf{y} \Vert_2 \leq \epsilon, $$ where ...
1
vote
2answers
170 views

Area formula for $n$-gon

Is there a formula for the area of a general polytope with $n$ vertices which just uses the distances between vertices, like Herons formel for the area of a triangle?
2
votes
0answers
59 views

Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices

I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e. ...
1
vote
0answers
101 views

Fast way to find a matrix with only $0$ and $1$ as entries full-rank or not?

I have a huge number of small Zero-One Matrices($4\times 4$, $5\times5$,$6\times6$) and I want to determine whether they are full-rank or not one by one. Gaussian elimination is a option, I want to ...
0
votes
2answers
199 views

Show a class of tridiagonal matrices is nonsingular.

I'm studying for an exam and came across a problem I can't seem to solve. The problem is as follows. Show that tridiagonal matrices ...
1
vote
0answers
497 views

Least Squares “analytic expression” for fitting a 2D quadratic function to measurements

I have n scattered elevation measurements: $ \{x_i,y_i,z_i\}_{i=1..n} $ that I want to fit a quadratic function to: $ z = ax^2 + by^2 + cxy + dx + ey + f$. The problem can be written as a vector ...
1
vote
1answer
133 views

Power iteration provably works if the matrix has a unique eigenvalue $\lambda$ and $\lambda>0$

Let $A$ be a $n\times n$ real matrix and $v_0 \in \mathbb R^n$ s.t. $||v_0|| = 1$. Define a sequence $(v_k)_k$ of $n$-dimensional real vectors by $v_k = A^kv_0 / || A^kv_0 ||$. Assume that $A$ has a ...
0
votes
3answers
87 views

Proving nonsingularity of a sum of matrices

I'm trying to solve this study question but I'm not sure how to proceed. The question is as follows. If \begin{equation}\frac{||B||_2}{||A||_2}<\frac{1}{\kappa_2(A)}\end{equation} with ...
3
votes
1answer
188 views

On minimizing matrix norm

Given $m\geq n \geq k$ and $A \in M^{m\times n}(\mathbb{C})$, the problem asks to evaluate $$\inf_{\textrm{rank}(B)\leq k}||A-B||$$ and gives condition on $A$ making the above minimum is taken by ...
2
votes
0answers
58 views

What is the significance of the matrix in the LAPACK logo?

This is the LAPACK linear algebra library logo: What is the significance of this matrix?
2
votes
1answer
153 views

What does it mean/imply that all my singular values are ones?

Suppose I apply SVD (singular value decomposition) on some real-valued matrix $M$, that is, $M = USV^T$. Now, if $S$ is an identity matrix, what does it mean? Does $M$ have some special properties? ...
1
vote
1answer
199 views

Solving commutator equation: $AX-XA=M$

Consider the field square matrices $M_n(\mathbb{C})$ or $M_n(\mathbb{R})$. I wish to solve the equation $AX-XA=M$ for a given $A,M$. Obviously this is just $n^2$ linear equations and thus is trivial ...
2
votes
2answers
58 views

Is this the correct solution?

Determine the coordinates of the vector $U=(4,5,-3)\;\text{of}\; R^3$ with respect to base ${(1,0,0), (0,1,0), (0,0, 1)}$ $$x(1,0,0) + y (0,1,0) + z (0,0,1) = (4,5, -3)$$ $$(x, 0,0) + (0, y, 0) + ...
0
votes
1answer
237 views

How do I calculate the values of the control points for an uniform cubic B spline surface?

I want to interpolate the following 3 scattered data points: (80.9,58.5,48.0),(35.0,89.6,82.3),(74.7,17.4,85.9) by an uniform cubic B spline surface on the following control lattice, $ \phi $: In ...
0
votes
1answer
85 views

matrix positive semidefinite

If $n \times n $ matrices $A, B$ are positive semi-definite, matrices $P$ and $Q$ are $n\times p$ and $n\times q$ matrices and their column vectors are orthogonal, which is to say $$P^{T}P=I_{p\times ...
1
vote
1answer
253 views

approximating diagonal of inverse sum of low rank and diagonal matrices

I was wondering if there is any theorem or algorithm to approximate the diagonal elements of the inverse of sum of low rank symmetric positive semi-definite and non-negative diagonal matrix. Let me ...
1
vote
0answers
79 views

Matrix in Matlab

I'd like to compute the centralizer of a subgroup $H$ of orthogonal group $O(8, R)$, so I need to solve the equation $AX=XA, BX=XB \mbox{ where } H=\langle A, B\rangle.$ The problem that I have is ...
1
vote
1answer
64 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
1
vote
1answer
786 views

Gaussian Elimination with Scaled Row Pivoting for numerical methods

I am solving a system first with basic Gaussian Elimination, and then Gaussian Elimination with scaled row pivoting (used in numerical methods) Basic Gaussian Elimination on the system $Ax=b$: ...
1
vote
0answers
162 views

Matrix spectral decomposition

Let $A$ be a square matrix $(N \times N)$ and $a_{ij} \in \mathbb{R}$. Suppose A has N eigenvalues $\lambda_{1} < \lambda_{2} < ...\lambda_{n} \in \mathbb{R}$. $A$ = $R \Omega R^{-1}$ its ...
2
votes
1answer
60 views

Numerical methods for inverting non positive definite matrices

I'm working on a PDE solver and need to invert the following matrix written in block form $\left( \begin{array}{cc} kM & -S \\ -S & M \end{array}\right) $ where M and S are the usual mass and ...
2
votes
1answer
74 views

Partial vs. full eigendecomposition when computing matrix logs with Matlab

I'm looking over a program that performs a matrix logarithm in each iteration, which necessitates looking at the eigendecomposition of the given matrix iterate $M^{(i)}$. However, rather than consider ...
-1
votes
1answer
987 views

LU factorization of a 2X2 singular matrix [duplicate]

My book is asking me to show that every matrix of the form $A=\begin{pmatrix}0&a\\0&b\end{pmatrix}$ has a $LU$-factorization and to show that even if $L$ is a unit lower triangular matrix that ...
1
vote
1answer
107 views

numerical linear algebra 101

since I'm a programmer and I need linear algebra, I'm starting considering how to teach myself a little of numerical linear algebra, not really optimize things right from the start, but I would like ...
0
votes
1answer
333 views

Spline Interpolation

I have four questions about splines. Any help would be greatly appreciated. 1) Boundary conditions for cubic spline interpolation to a set of data $a=x{}_{1}<x2<...<x_{m} , $ like for ...
0
votes
0answers
41 views

How to write a matrix equation for an underdetermined system

I am having difficulty writing the following equation in matrix form that I can then feed into a computer package to find solutions. The equation I have is: $f_i=g_i(1+\alpha*\exp(2*\pi*i*\lambda))$ ...
1
vote
1answer
53 views

Prefactoring to solve many similar linear systems

I am designing an algorithm that needs to solve many (large) linear systems of the form $$\Phi^\top D_i\Phi \vec x_i=\vec r_i,$$ where $\Phi\in\mathbb{R}^{m\times n}$ with $m>n$ is fixed. We will ...
0
votes
1answer
43 views

Simple question about equivalence of two forms of PCA as trace maximization over an implicit distribution

This may be a soft question of sorts. One formulation of principal component analysis is trace maximization: $$\arg\max_U \mathbb{E}_x \ [tr(U^Txx^TU)],$$ for $U^TU\le I$ and we assume that there is ...
1
vote
1answer
81 views

projection of a matrix $U$ with respect to the spectral norm of $UU^T$

I'm reading a paper that defines a projector as follows: $P_{\perp}(U)$ is a "projection" (slight abuse of termninology) with respect to the spectral norm of $UU^T$ onto the set of $d\times d$ ...
-1
votes
1answer
170 views

Positive linear combination of vectors to produce a positive vector

Given a list of vectors, I want a linear combination with positive coefficients that produces a final vector with only positive values (EDIT: this final vector is unknown; any positive vector is ...
4
votes
2answers
205 views

Is Householder orthogonalization/QR practicable for non-Euclidean inner products?

The question Is there a variant of the Householder QR algorithm to orthonormalize a set of vectors with respect to an inner product if no orthonormal basis is known a priori? Background Let's ...
0
votes
0answers
52 views

Minimizing an expression with linear constraints

Given a system of under-constrained (i.e. infinite solutions) linear equations (all values will be integers, all coefficients will be 0, 1, or -1), I want to pick values for the variables to minimize ...
1
vote
1answer
49 views

What is the range of this function

Let $\lambda_{1}(X)$ be the larger eigenvalue of the $2$ eigenvalues of a symmetric matrix X. For fixed real numbers $a,b,c,d$, what is the range of $\lambda_{1}\left(diag\left(a,b\right)-U\cdot ...
0
votes
1answer
39 views

$W(A)=\{x^HAx : x^Hx=1,{x\in \mathbb{C}}\}$, ${A\in \mathbb{R}}^{n\cdot n}$ How do I show that set is symmetrical set regard to real axis?

I need help to solve this task, so I would accept any suggestion: If ${A\in \mathbb{R}}^{n\cdot n}$, show that set $W(A)=\{x^HAx : x^Hx=1,\,{x\in \mathbb{C^n}}\}$, is a symmetrical set with respect ...
-1
votes
1answer
81 views

How do I show that $W(A)$ is symmetrical set regard to real axis? [closed]

I need help to solve this task,so I would accept any suggestion: If $A$ is $\mathbb R^{n\times n}$ squared matrix, show that $W(A)$ is symmetric set with regard to real axis.
0
votes
1answer
25 views

Given an M x N matrix, is there a way to produce an orthogonal set of N vectors of length M, where M < N?

Gram-Schmidt orthogonalization would only use the first M vectors to generate a basis of size M x M.
0
votes
0answers
47 views

Is there any risk to transform to $(B^{T} \otimes A)\operatorname{vec}(X)=\operatorname{vec}(C) $ for solving $AXB=C$ for X

To solve the equation $AXB=C$ for X, we can use the property of vec operator and kronecker product to transform to $(B^{T}\otimes A)\operatorname{vec}(X)=\operatorname{vec}(C)$, where ...
-4
votes
1answer
78 views

Can we conclude that this matrix is definite positive? [duplicate]

Let $A$ be a $n\text{-by-}m$ matrix. Suppose that columns of $A$ are linearly independent. Can we conclude that $A^TA$ is definite positive? Could you help me with proof? Thanks.
1
vote
0answers
334 views

What is the Moore-Penrose pseudoinverse for scaled linear regression?

The matrix equation for linear regression is: $$ \vec{y} = X\vec{\beta}+\vec{\epsilon} $$ The Least Square Error solution of this forms the normal equations: $$ ({\bf{X}}^T \bf{X}) \vec{\beta}= ...
1
vote
0answers
23 views

Short-cut to a group of long sums/differences

If I have data $a,b,c,d$, and want to calculate $x=a+b-c-d$, $y=a-b-c+d$ and $z=a+b+c-d$, I can save three adds by doing $e=a-c$, $f=b-d$, then $x=e+f$,$y=e-f$, $z=a+c+f$. If I have 100 data values ...
3
votes
1answer
327 views

How to show that the Hessian matrix of $G$ is positive definite?

Let $\{g_i:X\subset\mathbb{R}\rightarrow\mathbb{R};\;i=1,...,m\}$ be a linerly independet set of real functions. Given $n$ points $(x_1,y_1),...,(x_n,y_n)\in X$, consider the following function ...
2
votes
1answer
98 views

I would like a hint in order to prove that this matrix is positive definite

Let $a_{ij}$ be a real number for all $i,j\in\{1,...,n\}$. Consider the matrix below. $$B=\begin{bmatrix} \sum_{k=1}^n(a_{1k})^2 & \sum_{k=1}^na_{1k}a_{2k} & \cdots & ...
4
votes
1answer
92 views

$\delta$ Notation in linear algebra

In this equation below, what is $\delta_{l,q}$ denoting? Is $\delta$ a standard notation, or anything to do with all one's or the basis matrix etc? $$A_{ij}=\delta_{l,q}\left(\sum_{h=1}^n B_{l,h} + ...
2
votes
1answer
57 views

Numerical Methods for eigen values of $A \in \mathbb{C}^{n \times n} $

I've been writing a linear algebra library in c# for a while as an intellectual exercise and its gotten vastly more sophisticated that I originally thought it would and when I started adding methods ...
3
votes
1answer
230 views

Finding the smallest subset of a set of vectors which contains another vector in the span

Consider a set $S=\{ \underline{v_1},\dots , \underline{v_n} \} $ of vectors of dimension $d<n$. Suppose for some vector $\underline{b}$ that the solution space for the matrix equation $\left[ ...