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

learn more… | top users | synonyms

7
votes
1answer
2k views

Trace minimization with constraints

For positive semi-definite matrices $A,B$, how can I find an $X$ that minimizes $\text{Trace}(AX^TBX$) under 'either' one of these constraints: a) Sum of squares of Euclidean-distances between pairs ...
5
votes
3answers
2k views

Are there any decompositions of a symmetric matrix that allow for the inversion of any submatrix?

I am given a $J \times J$ symmetric matrix $\Sigma$. For a subset of $\{1, ..., J\}$, $v$, let $\Sigma_{v}$ denote the associated square submatrix. I am in need of an efficient scheme for inverting ...
6
votes
1answer
3k views

Block inverse of symmetric matrices

Let us assume we have a symmetric $n \times n$ matrix $A$. We know the inverse of $A$. Let us say that we now add one column and one row to $A$, in a way that the resulting matrix ($B$) is an $(n+1) ...
2
votes
2answers
101 views

How to prove the eigenvalues of tridiagonal matrix?

Assume the tridiagonal matrix $T$ is in this form: $$ T = \begin{bmatrix} a & c & & & &\\ b & a & c & ...
10
votes
2answers
1k views

Augmented Reality Transformation Matrix Optimization

i am a software developer, i'm working on an Augmented Reality system. I'd like to receive some advice in order to optimize my math model. My program has to be slim and fast. Here's the situation: ...
3
votes
2answers
404 views

Generating unitary matrices numerically - “close” to the identity element

EDIT: broke this into two parts - for these were two different questions. For numerically obtaining the stabilities of a matricial equation, i need to generate an ensemble of matrices that are ...
1
vote
1answer
182 views

Floating point arithmetic

How can I prove that : a real number has a finite representation in the binary system if and only if it is of the form $$\pm \frac{m}{2^n}$$ where n and m are positive integers.
4
votes
1answer
885 views

Product of positve definite matrix and seminegative definite matrix

Let $A$ a spd (symmetric positive definite) matrix and $B$ a symmetric seminegative definite matrix. Is tr $AB \leq 0$ and more general is $AB$ seminegative definite? I know that tr $AB \leq 0$ ...
2
votes
1answer
38 views

Choose $\rho$ such that $\rho$-norm minimizes the matrix condition number

I'm solving questions from am exam that I failed miserably, so I would love it if someone can take a look at my proof and make sure I'm not making any gross mistakes. Question Let $A$ a symmetric ...
2
votes
1answer
87 views

How to figure out the spectral radius of this matrix

$$A=\begin{array}{ccc} 0 & 1/2 & 0 & \cdots & 0 \\ 1/2 & 0 & 1/2 &\cdots& 0\\ 0 & 1/2 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots &\ddots ...
2
votes
1answer
110 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 & ...
3
votes
3answers
409 views

Inverse of constant matrix plus diagonal matrix

Is there an efficient way to calculate the inverse of an NxN diagonal matrix plus a constant term? I am looking at N of around 40000. $\left[\begin{array}{cccc} a & b & \cdots & b\\ b ...
1
vote
1answer
514 views

If modulus of each one of eigenvalues of $B$ is less than $1$, then $B^k\rightarrow 0$

Let $B$ be a $n\times n$ matrix and let $X$ be the set of all eigenvalues of $B$. Prove that if $|m|<1$ then $\lim \limits_{k\rightarrow\infty}B^k=0$, where $m=\max X$. Thanks. Actually, there ...
-4
votes
1answer
83 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.
5
votes
6answers
2k views

A book for self-study of matrix decompositions

I am a third year math student and I noticed that there are many uses for decomposing a matrix (I mean decompositions like SVD, LU etc'). Is there a good book for self-study of the subject ? Note ...
6
votes
2answers
10k views

Distance/Similarity between two matrices

I'm in the process of writing an application which identifies the closest matrix from a set of square matrices $M$ to a given square matrix $A$. The closest can be defined as the most similar. I ...
7
votes
1answer
174 views

Why would $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ be close to $A^{\dagger}$ when $A$ is with rank deficiency?

In many applications that is not with high requirements, it is common to use $(A^{\text T}A+\lambda I)^{-1}A^{\text T}$ or $A^{\text T}(AA^{\text T}+\lambda I)^{-1}$ ($\lambda$ is small) to ...
3
votes
1answer
727 views

Why SVD on $X$ is preferred to eigendecomposition of $XX^\top$ in PCA

In this post J.M. has mentioned that ... In fact, using the SVD to perform PCA makes much better sense numerically than forming the covariance matrix to begin with, since the formation of ...
3
votes
1answer
1k views

Factorize a Symmetric matrix as an 'Approximation' with an outer product.

(deprecated-taken back based on discussion(OLD)) What is a good way to factor a symmetric matrix $X$ as an outer product of two vectors $u$ and $v$. i.e, Find two vectors $u$ and $v$ such that ...
2
votes
3answers
76 views

Symmetry Of Differentiation Matrix

I have a problem computing numerically the eigenvalues of Laplace-Beltrami operator. I use meshfree Radial Basis Functions (RBF) approach to construct differentiation matrix $D$. Testing my code on ...
6
votes
1answer
54 views

Floating point arithmetic operations when row reducing matrices

A numerical note in my linear algebra text states the following: "In general, the forward phase of row reduction takes much longer than the backward phase. An algorithm for solving a system is usually ...
6
votes
4answers
212 views

Conditions for the equivalence of $\mathbf A^T \mathbf A \mathbf x = \mathbf A^T \mathbf b$ and $\mathbf A \mathbf x = \mathbf b$

I have an application where I have to minimize a cost function of the form: $J(\mathbf x) = \| \mathbf A \mathbf x - \mathbf b \|^2 \quad (1)$ By calculating the gradient, I derived that I have to ...
5
votes
1answer
157 views

QR factorization of a special structured matrix

A friend asked me the following interesting question: Let $$A = \begin{bmatrix} R \\ \xi{\rm I} \end{bmatrix},$$ where $R \in \mathbb{R}^{n \times n}$ is an upper triangular and ${\rm ...
4
votes
1answer
826 views

What is the time complexity of conjugate gradient method

I have been trying to figure our the time complexity of conjugate gradient method I have to solve a system of linear equations given by $$ Ax=b $$ where A is sparse and positive definite symmetrix ...
2
votes
0answers
43 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
2
votes
1answer
50 views

Strictly diagonal matrix

Suppose that matrix $A$ is strictly diagonally dominant, show that $$\|A^{-1}\|_{\infty}\leq\left[\min_i\left(|a_{ii}|-\left|\sum_{\substack{j\neq i}} a_{ij}\right|\right)\right]^{-1}.$$
2
votes
1answer
1k views

Fourier transform over a diagonal matrix

Let $F$ be a $100 \times 100$ DFT matrix, and $U$ be a diagonal matrix with its diagonal entries being all positive, denoted by $U=\mathrm{diag}(u_1, u_2,\cdots, u_{100})$. My question is: Under ...
1
vote
0answers
91 views

Really confused about LU decomposition and Doolittle algorithm

I'm really confused about the Doolittle algorithm, so I need some help. At the end of the description at wikipedia, it says It is clear that in order for this algorithm to work, one needs to ...
1
vote
0answers
103 views

Algorithm to determine matrix equivalence

I'm a physicist who's not particularly good at linear algebra so please accept my apologies if this is standard textbook stuff that I'm just unaware of. I have two real rectangular matrices $A_{mxn} ...
0
votes
1answer
77 views

Interpolation of polynomials

let $f(x)=2^x$ and $x_0=1$, $x_1=2$, $x_2=3$. Use divided differences to compute the interpolation polynomial $P(x)$ satisfying $P(x_i)=f(x_i)$, i=0,1,2 and $P'(x_1)=f'(x_1)$ and estimate error ...
0
votes
0answers
56 views

QR Algorithm with Shifts Question

Why must QR Algorithm with Shifts make no progress when applied to this n x n matrix? (attached as image). Also, if a matrix A is orthogonal in a QR factorization, will R be tridiagonal? How would ...
5
votes
2answers
2k views

When do two matrices have the same column space?

Recently I started learning about matrices and know for example that the pivot columns of a matrix form a basis for the column space of this matrix. I just can't seem to find out when two matrices ...
4
votes
1answer
480 views

3-sigma Ellipse, why axis length scales with square root of eigenvalues of covariance-matrix

This is my first post on math.stackexchange and i am not a mathematician, but i took some undergrad math courses and some grad mathematical modelling courses, so i come with a basic understanding of ...
4
votes
1answer
3k views

Linear least squares with inequality constraints

I'm trying to follow this older paper, page 19. The goal is to solve: $\min \|Ax-b\|^2 s.t. Gx \ge h$ given $A, G, b, h$ By combining the equations into a single LCP of the form: $Mz + q = w$ s.t. ...
3
votes
1answer
859 views

Unstable linear inverse problem: which “dampening” Tikhonov matrix should I use?

A linear inverse problem is given by: $\ \mathbf{d}=\mathbf{A}\mathbf{m}+\mathbf{e}$ where d: observed data, A: theory operator, m: unknown model and e: error. The Least Square Error (LSE) model ...
2
votes
1answer
408 views

equations solved with Newton's method by finding the zeros of functions?

I found this statement in one paper I read recently: This problem can be solved by finding the zero of functions: ...
2
votes
1answer
180 views

Finding vector $x$ so that $Ax=b$ using Householder reflections.

Assume $n\times m$ matrix $A$ and vector $b$ are given. I am looking for $x$ that satisfies $Ax=b$ in terms of linear least squares problem. Let $A=\begin{bmatrix} 1 & 1 & 1 \\0 & 1 & ...
2
votes
0answers
151 views

How to generate a random matrix which have given singular values?

I know one method: generate a random matrix, apply SVD decomposition, modify singular values, and then multiply those matrices back together. However, I'm wondering how random this method is. Since ...
2
votes
3answers
173 views

On integral of a function over a simplex

Help w/the following general calculation and references would be appreciated. Let $ABC$ be a triangle in the plane. Then for any linear function of two variables $u$. $$ \int_{\triangle}|\nabla ...
2
votes
2answers
455 views

Methods to solve a system of many Ax=B equations using least-squares

I am working with a force measurement instrument which needs calibration via a calibration matrix. For each of a set of controlled measurements I have a vector $k$ of three known, independent values, ...
1
vote
1answer
40 views

Strange behavior with coordinate transformation of square and quadrilateral

I am trying to map coordinates from a quadrilateral to a square. The coordinates are square: $(500,900)(599,900)(599,999)(500,999)$ quad: $(454,945)(558,951)(598,999)(499,999)$ where the $i^{th}$ ...
1
vote
0answers
37 views

Question on the uniqueness of LU decomposition

Let $A \in \mathbb{K}^{n \times n}$ a matrix, and suppose that we can run the Gaussian elimination on $A$ without row or column interchange, so there exist the $LU$ decomposition of $A$. We define ...
1
vote
2answers
106 views

Finding only first row in a matrix inverse

Let's say I have a somewhat large matrix $M$ and I need to find its inverse $M^{-1}$, but I only care about the first row in that inverse, what's the best algorithm to use to calculate just this row? ...
1
vote
1answer
612 views

Trapezoid Rule to Simpson's Rule Extrapolation

I need to show that one extrapolation of the trapezoid rule leads to Simpson's rule. I've looked through the other posts on ME, specifically the post with the same title, and this for help, but I ...
1
vote
1answer
67 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
2answers
113 views

Represent in a matrix form: $\sum_{ijl}(F_{il}-F_{jl})^2W_{ij}$

How can I represent this in a matrix form: $\sum_{ijl}(F_{il}-F_{jl})^2W_{ij}$ where all the entries are real and $W$ is a known(constant) matrix and $F$ is a rectangular matrix. When I say matrix ...
1
vote
2answers
122 views

Lanczos vectors

I am trying to implement the Lanczos algorithm. If I implement it in Fortran or C, (i.e. in finite precision), will the vectors generated at each iteration still preserve their linear independence? ...
1
vote
0answers
142 views

fixed point spectral radius

We have the following stationary matrix iteration $$x_{k+1} = Mx_k + c$$ where $M$ is nxn matrix and $c$ is a vector. Let $r(M)$ denote the spectral radius of $M$. Show that spectral radius ...
0
votes
0answers
37 views

Givens-Rotation from the right

i need to get a Givens-Rotation, which zeros a matrix entry when multiplied from the right side. I did already look at this topic givens rotation from right side but i could not really understand the ...
0
votes
0answers
105 views

Proof of theorem about iterative methods

How do I prove that if $A$ is a tridiagonal (or block tridiagonal) matrix then the corresponding $P_J$ and $P_G$ iteration matrices for the Jacobi and Gauss-Seidel methods satisfy that if $\lambda$ is ...