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

learn more… | top users | synonyms

-1
votes
1answer
2k 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
142 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
561 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 ...
1
vote
1answer
62 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
50 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
121 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
282 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
1answer
317 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
63 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
52 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 ...
-1
votes
1answer
41 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 ...
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
50 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
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.
2
votes
0answers
647 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
24 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
584 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
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 & ...
4
votes
1answer
132 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} + ...
3
votes
1answer
69 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
364 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[ ...
1
vote
1answer
113 views

Spectral radius of $A$ and convergence of $A^k$

I'm trying to understand the proof of first theorem here. Maybe it's very simple but I would like your help because I need understand this, I have no much time and my knowledge about this subject is ...
1
vote
0answers
200 views

How to Diagonalize an Extremely Large Sparse Matrix in SLEPc/PETSc

Dear Friends, Recently I have started with learning SLEPc/PETSc, but I didn't find a way to solve my problem. I have to solve a big sparse matrix which is a two dimensional quantum ...
1
vote
1answer
513 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 ...
2
votes
1answer
91 views

Radial coordinate evaluation

Details of the question can be found in the article equation(55,56) A radial coordinate $R$ defined by \begin{equation} r=\frac{2R}{\kappa(1-R^2)} \,, \end{equation} where $\kappa$ is a constantand ...
2
votes
1answer
194 views

The Miracle of Newton-Cotes

Background and motivation: Suppose I want to approximate the integral $\int_{a}^{b}f(x)dx$ using evenly-spaced sampled values of $f$: $f(a + \frac{i}{n}(b-a)), i=0,\cdots,n$. By the linearity of ...
3
votes
1answer
250 views

affine transformation of a polynomial

If I have a set of polynomials defined on six points of a triangle, such that $\phi_i(p_j) = \delta_{ij}$, how do I use an affine transformation to get new polynomials so that $\bar{\phi_i}(\bar{p}_j) ...
1
vote
2answers
327 views

Space spanned by matrices

I have a set of 5 by 5 matrices, M1,M2,...,M19 ,M20. I want to try to find a basis from this set and also to find relationships between these matrices. This is how I think I should approach the ...
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
1answer
115 views

What is the fastest algorithm to solve the eigenvector of a transition matrix of a Markov Chain?

Given a transition matrix of a Markov chain, $P$, I want to solve the left eigenvector of $P$, namely a row vector $\alpha$ such that $$ \alpha P = \alpha $$ I know the algorithm to solve a linear ...
1
vote
1answer
213 views

How to find the unknown values in this Numerical Integration type?

Given the following type of numerical integration: $$I(f)=\int_0^1 f(x) \, dx \approx \frac 12 f(x_{0}) +c_1 f(x_1) $$ a) Find the values ​​of: the coefficient $c_1$ and points $x_0$ and $x_1$ so ...
1
vote
0answers
133 views

Existence criteria for the LU decomposition of a tridiagonal matrix

In this link, the following result is presented without proof: Let $a, b, c$ be the lower off diagonal, diagonal, and upper off diagonal elements of a tridiagonal matrix. A pivotless LU ...
2
votes
3answers
584 views

Non-monotonic decrease of residuals in Conjugate Gradients:

In some of my numerical programming using conjugate gradient solvers, I noticed an alarming problem: The residuals were not monotonically decreasing to zero, but were sometimes increasing. In this ...
1
vote
0answers
294 views

About the Generalized singular value decomposition (GSVD).

I have studied about Singular value decomposition (SVD) and had solved few numerical examples to understand SVD. Now I am studying Generalized singular value decomposition (GSVD). I followed this ...
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 ...
3
votes
0answers
90 views

Solver for sparse linearly-constrained non-linear least-squares

Reposted from stackoverflow on the advice of Nick Rosencrantz: Are there any algorithms or solvers for solving non-linear least-squares problems where the jacobian is known to always be sparse, and ...
1
vote
0answers
39 views

Algorithm to compute similarity computation

I have a similarity transformation of matrices from the type $B = P^{-1}AP$. It is known that $A$ and $P$ are invertible matrices, but not orthogonal. Given that I have the matrices $P$ and $A$ I ...
2
votes
1answer
160 views

Block matrix notation

Given that $A$ is a real, rectangular matrix of dimension $m \times n$ and $\begin{align} A = \left[\begin{array}{c} I \\ e^{\intercal} \\ -e^{\intercal}\end{array}\right] \end{align}$ is represented ...
1
vote
2answers
143 views

solving linear recurrence - general solution confusion

I've been trying to get my head around this for days. I understand what is going on with the calculation of a linear recurrence and I also understand how the characteristic is obtained. What is ...
3
votes
1answer
127 views

About iterative refinement to the solution of the linear equations

I want to know what is iterative refinement for improving the solution to the linear equations? How they improve solutions and what are the various techniques for the iterative refinements? Any ...
1
vote
0answers
430 views

Multigrid Interpolation and Restriction operators

I have a question about the restriction and the interpolation operators of a Multigrid algorithm. Let those be given: The full weighting restriction stencil (in 2D): $\frac{1}{16} \left[ ...
1
vote
2answers
319 views

error for Conjugate gradient method

Suppose A is a real symmetric 805*805 matrix with eigenvalues 1.00, 1.01, 1.02, ... , 8.89,8.99, 9.00 and also 10, 12, 16, 36 . At least how many steps of conjugate gradient iterations must you take ...
5
votes
1answer
954 views

Sum of eigenvalues and singular values

How one can prove that for a matrix $A\in \mathbb{C}^{n\times n}$ with eigenvalues $\lambda_i$ and singular values $\sigma_i$, $i=1,\ldots,n$, the following inequality holds: $$ \sum_{i=1}^n ...
0
votes
1answer
69 views

$\lambda_{min}\left (\frac{A+A^*}{2} \right )\leq \sigma_{min}(A)$

For $A \in \mathbb{C}^{n \times n}$, how to show that $\displaystyle \lambda_{min}\left (\frac{A+A^*}{2} \right )\leq \sigma_{min}(A)$?
2
votes
2answers
975 views

Minimum eigenvalue and singular value of a square matrix

How to show that the relationship $\left | \lambda_{min} \right | \geq \sigma_{min}$ holds between the minimum eigenvalue and singular value of a square matrix $A \in \mathbb{C}^{n \times n}$?
1
vote
0answers
54 views

Preconditioning and effects on precision of solution of LSE

In my courses on numerical analysis I have been tought that the main and principle motivation for preconditioning linear systems of equations is to increase the convergence rate of iterative solvers ...
0
votes
1answer
439 views

Largest and smallest eigenvalues of a hermitian matrix

How to show that the largest and smallest eigenvalues of a hermitian matrix $A \in \mathbb{C}^{n \times n} $ can be found as: $\displaystyle \lambda_{max} = ...
0
votes
1answer
306 views

What is the error in Newton's Method for Matrix Inversion?

I need it to invert a matrix. Wikipedia explains that there is a generalization of the Newton Method for matrices. However, there is nothing mentioned about the error bounds. Suppose we have, as ...
1
vote
1answer
963 views

Underdetermined linear systems least squares

I have an underdetermined linear system, with 3 equations and four unknows. I also know an initial guess for these 4 unknows. The article I am reading says: We can solve the system using the least ...
0
votes
1answer
1k views

Condition number for non-square matrix?

From what I understand the condition number of a non-square matrix A is its largest singular value divided by its smallest nonzero singular value: $\kappa(A) = \sigma_1/\sigma_n $. Where ...