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

learn more… | top users | synonyms

0
votes
3answers
87 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
150 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
549 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
328 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
820 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
73 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
743 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
207 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
381 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
149 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
776 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
652 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
366 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
173 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
3k 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
297 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
285 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
92 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 ...
2
votes
2answers
472 views

Prove: existence of solution of $Ax = b$ by least squares

I'm studying for my exam of linear algebra.. I want to prove the following corollary: Given $A \in{R^{m\times n}}$, there is always a solution $x$ to $Ax = y$ for the least-squares minimization ...
1
vote
1answer
511 views

Prove: Full Rank and a solution os linear system

I'm studying for my exam of linear algebra.. I want to prove the following corollary: Given $A \in{R^{n\times n}}$, there is a solution $x$ to $Ax = y$ for all $y$, if and only if $A$ has rank ...
1
vote
1answer
129 views

Safe use of generalized inverses

Suppose I'm given a linear system $$Ax=b,$$ with unknown $x\in\mathbb{R}^n$, and some symmetric $A\in\mathbb{R}^{n\times n}$ and $b=\in\mathbb{R}^n$. Furthermore, it is known that $A$ is not full-rank ...
3
votes
1answer
124 views

Orthogonality, Maximization and Eigen-Solution

I Have read that for a matrix of reals $Y$ and a p.s.d matrix $B$ that the Maximum of $ f(Y)=Tr(Y^TBY)$ subject to $Y^TY = I$ is achieved when $span(Y)$ equals the span of the first $d$ ...
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
608 views

Fast algorithm for LU factorization

If A is a symmetric matrix, is there a fast algorithm for LU factorization? I know this algorithm for non-symmetric matrix. ...
0
votes
1answer
94 views

Iterative Method for a special kind of Sparse Matrix

I've the following problem.I've a sparse square Matrix $\bf M$. I can write $\bf M$ as: $${\mathbf M} = \begin{bmatrix}\mathbf A_{11} & \dots & \mathbf A_{1n} \\ \vdots & \ddots & ...
0
votes
1answer
112 views

Choosing initial approximation for computing Moore-Penrose inverse

I am trying to compute the Moore- Penrose inverse of a given $m\times n$ matrix $A$. I did convergence analysis then I came across to the following condition. For convergence of my method: $\max\mid ...
4
votes
1answer
366 views

Solving for specific entries in a Lyapunov Equation

Let $A$ be a $2n\times 2n$ real matrix with the following structure \begin{equation} A = \left(\begin{matrix} 0 & -I \\ K & S \end{matrix}\right) \end{equation} with all sub-matrices of size ...
1
vote
2answers
503 views

Solving linear system of equations when one variable cancels

I have the following linear system of equations with two unknown variables $x$ and $y$. There are two equations and two unknowns. However, when the second equation is solved for $y$ and substituted ...
4
votes
2answers
361 views

Incremental approach of calculating the Singular Value Decomposition

I have a fairly large array, a billion or so by 500,000 array. I need to calculate the singular value decomposition of this array. The problem is that my computer RAM will not be able to handle the ...
2
votes
1answer
335 views

Is the Neumann series of a real semidefinite matrix asymptotic?

Let $A \in \mathbb{R}^{m \times m}$ be a real symmetric negative-semidefinite matrix and consider the Neumann series $$\sum_{k=0}^\infty t^kA^k = I + tA + t^2 A^2 + \cdots$$ where $t > 0$ is a ...
5
votes
0answers
448 views

Simulating from a Multivariate Gaussian without Cholesky

I'd like to draw a sample from a multivariate Gaussian distribution $\mathcal{N}(\mu, \Sigma)$, where $\mu$ is the mean vector (can assume it to be $\boldsymbol{0}$), and $\Sigma$ is a sparse positive ...