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

learn more… | top users | synonyms

4
votes
1answer
151 views

In terms of complexity, is there a quicker way of checking if a matrix is nonsingular than computing the determinant?

To repeat the question, let $A$ be a square matrix. We wish to determine if $A$ is nonsingular, that is, invertible. One way is compute its determinant and check if it is nonzero. However, if $A$ is ...
0
votes
2answers
283 views

Convergence of CG method

I have a question like how can we mathematically prove that for a general matrix Conjugate Gradient method will always converge within n steps in exact arithmetic ? where n is the size of the matrix. ...
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 ...
1
vote
1answer
474 views

Does conjugate gradient converge for negative definite matrices?

Guys I was reading about CG method to solve the sparse systems. I came across that the method is defined for positive definite symmetric matrices. I was wondering does it converges for negative ...
1
vote
1answer
344 views

pseudo-inverse of a matrix as a projection?

Is there an interpretation of $X^{\dagger}Y$ in terms of a projection or a least-squares formulation? Note that $\dagger$ denotes the pseudo-inverse and $X$ is a square matrix, and $Y$ is a ...
0
votes
1answer
63 views

Is it a positive semi-definite matrix?

Given a p.s.d matrix $K$, is $2\operatorname{Diag}(K)-K$ a p.s.d matrix? Here, $\operatorname{Diag}(K)$ is a diagonal matrix whose diagonal is the diagonal of $K$.
2
votes
0answers
80 views

Spectral/ Eigen-Value solution with a linear constraint?

Is there a spectral or eigen-value solution to finding $X$ such that $Tr(CX^TMX)$ is minimum for a symmetric matrix $C$ and a p.s.d matrix $M$. Also there is a linear constraint on the minimization ...
1
vote
2answers
1k views

Moore-Penrose pseudo inverse algorithm implementation in Matlab

I am searching for a Matlab implementation of the Moore-Penrose algorithm (convertable to C++) computing pseudo-inverse matrix. I tried several algorithms, "Fast Computation of Moore-Penrose Inverse ...
1
vote
1answer
146 views

trace function, eigen decomposition and optimization!

The equation \begin{align} \min_{X}~trace(CX^{T}MX) \end{align} where $C$ is symmetric and M is symmetric , p.s.d can be minimized by defining $M=F^{T}F$ ($M$ being a psd matrix, you will be able to ...
2
votes
1answer
85 views

Determining function inputs when outputs are recursively related to each other

I have a vector $\bf{b}$, and elements of this vector are generated by evaluating a rather complicated function $f(x)$ for $f(x_0), f(x_1),...,f(x_N)$. Here are the equations that constitute $f(x)$. ...
1
vote
2answers
90 views

Spectral/Eigen-value solution?

Is there a spectral or eigen-value solution to finding $d$ vectors $x_1...x_n$ such that $ \sum_{i,j=1}^{d} C_{i,j} \cdot x_i^\top M x_j $ is minimized, with $C_{i,j}$ being a constant real-scalar ...
2
votes
2answers
453 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, ...
0
votes
2answers
39 views

Efficiently updating a vector

What is the most efficient way to make this linear algebra computation? I am interested in computing a vector $y^{(k)}$ that updates as shown below. $$y^{(k)} = A^k B A^k x$$ where the matrices $A,B ...
0
votes
3answers
88 views

Why change a given basis?

Why would we want to transform a vector in our normal basis (xyz axes) to another basis? The only situation I can recall is when we are looking at a force applied on an inclined plane. Are there any ...
1
vote
2answers
154 views

Difference between lsq(A,b) and A\b (on Scilab)

Can you explain me the difference between lsq(A,b) and A\b? Why do I get a positif solution when I use lsq(A,b,1)? Where can I get the source code of lsq function? Thank you.
0
votes
3answers
338 views

$A+\lambda B $ is invertible

I stumbled upon this question that I would like to ask you about: Let $A$ be a $n\times n$ matrix $(\mathbb R)$ and $B$ an invertible Matrix of size $n$ with real coefficients. I need to show that ...
9
votes
6answers
550 views

$\left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} \right)$ not diagonalizable

I would like to ask you about this problem, that I encountered: Show that there exists no matrix T such that $$T^{-1}\cdot \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \\ \end{array} ...
3
votes
2answers
336 views

Are Trace of product of matrices- distributive/associative?

Is $\operatorname{Tr}(X^TAX)-\operatorname{Tr}(X^TBX)$ equal to $\operatorname{Tr}(X^TCX)$, where $C=A-B$ and $A$, $B$, $X$ have real entries and also $A$ and $B$ are p.s.d.
1
vote
0answers
142 views

Show that its a Generalized Eigenvalue problem

Show that the minimizer is obtained by a generalized eigenvalue problem. $$\alpha=\underset{1^TK\alpha=0; \ \alpha^TK^2\alpha=1}{\text {arg min}} \gamma ||f||_{K}^2+f^TLf$$ Details: $K$ ...
2
votes
3answers
853 views

Least norm solution to $Ax = b$

How to prove that if you have $x^*$ such that $x^*=\text{psuedoinverse}(A) b$, and $Ay=b$, then $$\Vert x^* \Vert_2 \leq \Vert y \Vert_2$$
3
votes
1answer
74 views

Compute Cholesky of $\Sigma^{-1}$ from Cholesky of $\Sigma$

Given a positive definite matrix $\Sigma$, how can I compute the Cholesky decomposition of $\Sigma^{-1}$ from the Cholesky decomposition of $\Sigma$? I know that $\left(L L^T \right)^{-1} = ...
2
votes
1answer
750 views

Matlab Matrix Multiplication Calculate Significant Figures

First off, long time reader, first time poster. Thanks in advanced for all the help this site has offered! So the question! I have two matrices in the form of the variables ...
1
vote
1answer
211 views

Simultaneous Eigenvalue Problem

I have what I think is a simultaneous eigenvalue problem in three parameters: $$\alpha A_1x + \beta B_1x + \gamma C_1x + D_1x = 0$$ $$\alpha A_2x + \beta B_2x + \gamma C_2x + D_2x = 0$$ $$\alpha A_3x ...
1
vote
1answer
388 views

SVD and linear least squares problem

Edit: I've actually found an error: Instead of full SVD I had to use, "economy size" SVD, where $U$ has only first $n$ columns, and $\Sigma$ becomes a square matrix. I also forgot to take the ...
1
vote
0answers
54 views

Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
1
vote
1answer
125 views

How to get around non-commutativity of matrix multiplication?

I have a problem with a matrix equation/transformation problem which I need solving. I have two transformations $A_1$ and $A_2$, both of which can be expressed as $A_i = R_i \times B_i$, $R_i$ ...
4
votes
1answer
150 views

What does “overdetermined” mean

When we say a problem is an overdetermined system, what do we mean by that in a rigorous fashion? Thanks.
1
vote
2answers
2k views

Uniqueness of symmetric positive definite matrix decomposition

We know that any symmetric positive semi-definite matrix $K$ can be written as $K= AA^T$, where $A$ has real components. One way to get to $A$ is to compute eigen value decomposition of $K= P^T DP$ ...
2
votes
2answers
4k views

Linear independent sets of non-square matricies

I'm having problems with the best way to work out linearly independent sets of matrices. When the set can be made into a square matrix, such as $ \begin{bmatrix} 1 \\ 0\end{bmatrix}, \begin{bmatrix} ...
2
votes
3answers
1k views

Approximate a convolution as a sum of separable convolutions

I want to compute the discrete convolution of two 3D arrays: $A(i, j, k) \ast B(i, j, k)$ Is there a general way to decompose the array $A$ into a sum of a small number of separable arrays? That is: ...
4
votes
2answers
789 views

Why does the standard BFGS update rule preserve positive definiteness?

My class has recently learnt the BFGS method for unconstrained optimisation. In this procedure, we have a rank-1 update to a positive definite matrix at each step. This is specified as: $H_{k+1} = ...
1
vote
2answers
678 views

How to prove whether a function is linear or affine?

so i am having hard time understanding the idea of coming up with random n-vectors to disprove the superposition equality $f(\alpha x + \beta y) = \alpha f(x) + \beta f(y)$. or to prove that a ...
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 ...
4
votes
1answer
369 views

principal “pseudo eigenvector” of a real symmetric positive-semidefinite matrix

Let $A$ be a real symmetric positive-semidefinite matrix and suppose that $c>0$ is a sufficiently small number. I wonder if it is possible to solve the non-convex optimization $$\arg\max_u\ ...
0
votes
0answers
181 views

Divide and conquer possible on linear equation systems?

Suppose a 4-connected regular grid $$\mathcal{G}=(\mathcal{E},\mathcal{V}),$$ where $\mathcal{E}$ and $\mathcal{V}$ denote the set of edges and vertices of that grid, respectively. Given this ...
5
votes
1answer
4k views

Properties of sum of real symmetric, positive semi-definite matrices

I have two correlation matrices A and B. They are: Real symmetric (with ones on the diagonal) Positive semi-definite (eigenvalues are $\ge 0$) I want to try to prove that the average of these two ...
1
vote
0answers
298 views

Finding a row permutation that makes a matrix more “blocks-like”

Disclaimer: what follows arise in a context from Computer Science, but it seems to me that my questions were more likely to be solved from mathematicians than from computer scientists. Let suppose ...
8
votes
1answer
1k views

What would be a good method for finding the submatrix with the largest sum?

This question is from an ongoing contest which ends in 4 days. It is this problem from the October Challenge. Given:A Matrix (Not necessarily square) filled with negative and positive ...
1
vote
1answer
63 views

Eigenvalues, Eigenvectors and Eigendecomposition

If there is a symmetric matrix, say $$B = \left[\begin{array}{cc} 0 & A\\ A^T & 0 \end{array}\right]$$ where $A$ is a $m\times n$ submatrix with $m \geq n$. Is it possible to express the ...
0
votes
1answer
2k views

Covariance Matrix in Weighted Least Square Estimation

I am new to linear algebra and I have the following doubts: In weighted least square estimation of the system $Ax = b$ we minimize the weighted value of the error $e = b - Ax$ and the best $\hat{x}$ ...
6
votes
1answer
166 views

Computing very high powers of a particular Jordan block

Let $J$ be the following $k-by-k$ Jordan block: $$ J:= \begin{bmatrix} e^{i \theta} & 1 & \\ & e^{i \theta} & 1 \\ & & \ddots & \ddots \\ & & & \ddots & ...
1
vote
1answer
48 views

Multiplications by unimodular matrices

I feel like this must have an obvious answer, but my knowledge of integer arithmetic is limited. Given an (integer) matrix $A$ of dimension $m \times n$ and an unimodular matrix $U_l$ of dimension $m ...
2
votes
0answers
137 views

The norm of the matrix

This problem is in Trefethen'book Numerical Linear Algebra Suppose the $m\times n$ matrix $A$ has the form $A=\begin{pmatrix}A_1\\A_2 \end{pmatrix}$ where $A_1$ is a nonsingular matrix of dimension ...
2
votes
1answer
1k views

How to remove linearly dependent rows/cols

How would one remove linearly dependent rows/columns from a rank-deficient matrix. For example, (from wikipedia): $$ A = \begin{bmatrix} 2 & 4 & 1 & 3 \\ -1 & -2 & 1 ...
0
votes
1answer
80 views

relative error relation

Let $x$ be a non-null quantity. Let $\hat{x}$ be its approximation. I am trying to find the relation between: $\frac{\left | x-\hat{x} \right |}{\left | x \right |}$ and $ \frac{\left | x-\hat{x} ...
1
vote
1answer
287 views

Similar matrix proof

$A$ and $B$ are similar matrices, if $B=PAP^{-1}$ holds for a square, non-singular matrix $P$. Now am wondering if $S^{-1}T$ and $S^{-1/2}TS^{-1/2}$ are similar matrices? Am looking for a proof for it ...
0
votes
1answer
202 views

Solution for a Frobenius norm inequality

Am trying to find a real scalar $\gamma$ such that for a given pair of real rectangular matrices $X,Y$ the following holds: $\frac{||Y||_{F}^{2}}{5} \leq ||\gamma X||_{F}^{2}\leq ||Y||_{F}^{2}$ ...
0
votes
1answer
93 views

Scalar multiplication and Frobenius norm

Was wondering on what would be the real number (scalar) $\gamma$ that needs to be multiplied with each entry in a real rectangular matrix $X_{m\times n}$ such that the Frobenius norm of $X$ equals a ...
2
votes
2answers
3k views

Finding a coefficient of a unknown to have a unique solution in a system

I am resolving the following matrix: 1 2 1|1 -1 4 3|2 2 -2 a|3 Where I have to find all the values of $a$ so that the system can have a unique solution. ...
0
votes
2answers
73 views

solving a matrix equation $X-I=a \cdot (X\cdot U^T + U \cdot X)$

I am trying to solve the $n \times n$ diagonal matrix $X$ in the following equation: $$X-I=a \cdot (X\cdot U^T + U \cdot X)$$ where $0<a<1$ is a given scalar, $U$ is a $n \times n$ given ...