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

learn more… | top users | synonyms

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
346 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
352 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
102 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
241 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[ ...
0
votes
1answer
92 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
140 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
319 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
88 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
155 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
148 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
168 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
1answer
78 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 ...
0
votes
0answers
73 views

Shear decomposition

Is there an algorithm for decomposing a square matrix (or a similar matrix to it) in to shear and diagonal matrices? All the usual decompositions (Schur, SVD, QR, LU, etc.) don't seem to help. ...
1
vote
1answer
86 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
134 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
97 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
293 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
172 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
148 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
68 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
36 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
82 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
99 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
112 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
224 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[ ...
0
votes
2answers
203 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 ...
4
votes
1answer
669 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
55 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
527 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
47 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
267 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
199 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
555 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
634 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 ...
2
votes
1answer
55 views

Problems where SPD linear system arises

I know some of the places where SPD linar systems arises such as elliptic PDEs and normal equations. Can I have a more comprehensive list of scientific applications which require solving SPD linear ...
3
votes
1answer
297 views

Polynomial Condition Number

I have a question, from "Applied Numerical Linear Algebra"(James W. Demmel), that I don't know how to do. Consider $\mathbb{R^{d+1}}$ as the set of polynomials of degree $\leq d$ and $S_a$ the set of ...
4
votes
2answers
437 views

Matrix Calculus in Least-Square method

In the proof of matrix solution of Least Square Method, I see some matrix calculus, which I have no clue. Can anyone explain to me or recommend me a good link to study this sort of matrix calculus? ...
4
votes
1answer
66 views

Help in Proving a theorem

For the last few days I am trying to prove Result 2 which I have written below that uses the concepts of matrix decompostions to write matrix $A$ in the block form. I need help to prove this ...
2
votes
1answer
465 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 ...
0
votes
1answer
104 views

Solve: This System of equations for $X$ (does a real solution, exist?)

How can I solve $AX + diag(X)[I-c]=0$ for $X$? All matrices have real entries, $diag(X)$ is a diagonal matrix with the diagonal entries being the diagonal entries of $X$, and $c$ is a constant, real ...
1
vote
1answer
386 views

How to find the Householder transformation?

Assume $x=(1,0,4,6,3,4)^T$. Find a Householder transformation and a positive number $\alpha$ such that $Hx=(1,\alpha,4,6,0,0)^T$. I'm sorry that I don't know how to start with this problem. A ...